Принцип действия решета:
Другая задача, которую решили математики Древней Греции — нахождение всех простых
чисел в интервале от 1 до заданного числа N. Самым быстрым и поныне считается алгоритм
Эратосфена (275-195 гг. до н.э.). Существует предание, что Эратосфен выписал в ряд на папи-
русе все натуральные числа и затем прокалывал каждое второе (то есть делящееся на 2), потом
— каждое третье, и т.д. В конце этой процедуры остаются «непроколотыми» только простые
числа, которые делятся только на себя и на 1.
Вместо папируса мы будем использовать массив A, в котором элемент A[i] для всех i от
1 до N принимает два возможных значения:
1, число «не проколото» и является кандидатом на простые;
0, число «проколото» и больше не рассматривается.
Вопрос:
Зачем прокалывать каждое второе я понял - если их проколоть, останутся нечетные (делятся на 1 и на себя).
А вот зачем прокалывать потом каждое 3-е, потом каждое 4-ое?

1  2  3  4  5  6  7  8  9  10  11  12
    x      x      x      x        x          x        //каждое второе
        x          x          x                x        //кажое 3-е
            x              x                    x       //каждое 4-ое



После ввода числа аварийно завершается программа.
Непонятные моменты:
for (i = 1; i <= N; i++) A[i] = 1;
1) Вводили указатель *A, тут получился уже массив A[i]
2) В массиве A[i] i-ый элемент будет равен единице. Что-то не так   

Это сообщение отредактировал(а) n199a - 7.7.2013, 20:43

где? Его не вводили, а определяли.
когда ты выделил память с помощью new ты получил динамический массив на N+1 элемент
кстати, в языке Си массивы индексируются с 0.

Вот нечётные не обязательно делятся только на 1 и на себя. Рассмотрите такие числа как 9, 15, 21, 25 и т.д.


Как раз, чтобы исключить числа, которые делятся на 3,4 etc.


Ну как бы это сказать... Если путать "равно" и "двойное равно"...

Более того, не нужно проверять на NULL значение, возвращаемое от new (в случае нехватки памяти будет брошено исключение).



А что тут непонятного... Инициализируется массив единицами (как бы изначально считаем, что все числа - простые, а потом исключаем составные путём  A[i] = 0).

Добавлено через 1 минуту и 52 секунды

Тут просто значение индекса и значение числа - одно и то же (это разумно для этой задачи), 0-ой индекс не используется, а памяти выделяется на 1 элемент больше

  

feodorv, я заметил.   

Что означает - брошено исключение?
В учебнике пишут, что, может затереться любой участок памяти и произойдёт непредвиденный сбой.

Если так прокалывать, то проколются ВСЕ числа, смотри:
1  2  3  4  5  6  7  8  9  10  11  12
    x      x      x      x        x          x        //каждое второе
        x          x          x                x        //кажое 3-е
            x              x                    x       //каждое 4-ое
                x                    x
                   x                            x
                        x
                            x
                               x
                                    x
                                            x
                                                  x
Что тут исключается? В итоге то полностью каждое число проколется. Что останется?

Добавлено @ 12:10

Не понял намек.
Я про то, что, после ввода числа вылазит ошибка (отправить отчет и не отправлять отчет об ошибке). Т.е. программа нерабочая. Я в этом смысле. Что тут не так, может у вас нормально будет?

Это сообщение отредактировал(а) n199a - 8.7.2013, 12:12

• Вам говорят, что строчка №8 не нужна, так как данная операции никогда не венет NULL (о хаках, и переопределения, и особых вызовах  пока не говорим).
• текущая строчка №8 и делает вам креш!!! if (A = NULL) - это не сравнение, а присваивание, о чем вам и писали, когда говрили, что вы путаете операции. Для правильности if нужно изменить так: if (A == NULL) или так if (!A)

Это сообщение отредактировал(а) SenkraD - 8.7.2013, 13:02

Ну всё же кристально ясно. = это присваивание, == а это сравнение. И что делаете Вы?

Вы присваиваете (не сравниваете!!!) указателю A значение NULL (то есть 0). Получается, что Ваш код эквивалентен такому
Поскольку 0 - это всегда "ложь", то программа продолжает работать дальше, но уже с A, равному NULL. И что дальше? А дальше

То есть попытка присвоения значения по нулевому указателю. А это даёт то самое

Правильно так:
Двойное равно, однако   



Если указатель имеет мусорное значение (какое-то произвольное, от балды), то да. Если как у нас - вполне определённый 0 (NULL), то однозначно произойдёт сбой (ничего затираться не будет). В этом великая сила нулевого указателя (ну и ряда других специальных значений).



Вам сюда. Выкиньте вообще эту строчку с проверкой на NULL.



Ну Вы тогда не поняли смысл решета. Не каждое  

Где здесь каждое? Для 40:


PS Пардон, что на "вы", не заметил, что можно на "ты".

Добавлено через 31 секунду
SenkraD,   

Если не ошибаюсь, здесь можно поствить умножение.
Будет быстрее.
for (i = k*k; i <= N; i += k)

и если new заменить на malloc, то будет программа на С.
(а так ни рыба, ни мясо.)

Не))) Нужно пройтись по всем кратным k: 2k, 3k, 4k ... до N (по мере возможности))) Так исключаются составные числа, в разложение которых входит k. Само k не берём в рассмотрение, так как оно как раз простое (кроме единицы, которая не входит в цикл, так как отсчёт начинается от 2, но которую, по большому счёту тоже стоит исключить из списка простых чисел) из-за проверки   

(а если A[k] равно 0, то k - составное, и смысла в просеивании нет - уже всё просеяно до нас)))



Это да   

feodorv, допустим в какой-то момент k = 7
Зачем проходицца по 2*7, 3*7, 4*7 ?
Прежде чем к стало 7, оно было 2, 3, 4 и т.д.
То есть, числа кратные 2,3,4,5,6 уже и так зачеркнуты.
Первое число которое может быть не зачеркнутым это 7*7
Следовательно можно начинать сразу с 7*7
Разве нет?

Добавлено @ 01:37
Щас поздно уже, мозги не варят, завтра проверю.


Это сообщение отредактировал(а) volatile - 9.7.2013, 01:40

Ха, а ведь весьма даже может быть!!!
Мда, век живи, век учись   

Ну собственно, проверять и нет особой необходимости. В википедии алгоритм так и приведен :

Решето Эратосфена

Кстати, для n199a, там есть гиф-анимашка, поясняющая работу, возможно поможет вам понять.