Простые числа, где можно найти ряд Опции

[ig_z]

Подскажите, где можно найти ряд простых чисел. От 1000 и дальше. Поиском найти не смог.

[DRUID3]

Подскажите, где можно найти ряд простых чисел. От 1000 и дальше. Поиском найти не смог.

Вы бы еще формулу попросили...

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Finding prime numbers
//  (c) Johna Smith, 1996
//
//  Method description:
//   We take a number and try to divide it. If we can divide it
//   without remainder - this is not prime number.
//   We can take into account only odd numbers, because we can
//   divide all even number by 2. Also we can store all prime
//   numbers that are already found in an array and try to divide
//   all new numbers only by numbers from this array.
//   If we want to find all prime numbers less than N the size of
//   the array should be sqrt(N)/2
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

#define N   160  // so we can find all prime numbers that are less than 100000
#define M   25   // check all numbers less than 250

int Simple[N];
int k=0;
enum {yes,no} simple;

void main(void)
{
// it's easy: 2 and 3 are prime
if (M>=2) printf("2\n");                    // 2 is simple 'cause we can divide it only by itself and 1
Simple[k++]=2;
if (M>=3) printf("3\n");
Simple[k++]=3;

// but what we can say about other numbers:
for(int i=5; i<=M; i+=2)
{
   simple=yes;
   for(int j=0; j<k; j++)
   {
     if (Simple[j]*Simple[j]>i) break;     // other Simple[j] is too big for i
     if ((i%Simple[j])==0) simple=no;    // there's no remainder - not prime
   }
   if (simple==yes)
   {
     printf("%d\n",i);
     Simple[k++]=i;
   }
}
}

Это я копирнул с "винграда", раздел "алгоритмы".

P.S.: Кстати, о формуле простых чисел ( ), вот человек получил кое какие аппроксимации ряда (я сам не проверял, т.к. довольно холоден к фундаментальной математике). Но если надумаете, как их применить в прикладных задачах - Вам и карты в руки...

[ig_z]

Подскажите, где можно найти ряд простых чисел. От 1000 и дальше. Поиском найти не смог.

Вы бы еще формулу попросили...

Спасибо за ответ. Я еще более холоден к данной теме. Просто просьба со стороны.

Что касается формульного расчета, то действительно гарантировано простое число на выходе. Но, если я не ошибаюсь, нет гарантии, что будет рассчитан весь ряд без пропусков. Вроде я слышал, что раньше публиковали полные ряды, получаемые тупым перебором. Вот такое бы найти.

[Andrew10]

В Mathematica-5.2 функция Prime[n] дает n-ое простое число. Расчет чисел с номерами от 1000 до 10000 на Pentium, 1.7 ГГц занял 0.015 секунды (без вывода на экран или в файл)

[DRUID3]

В Mathematica-5.2 функция Prime[n] дает n-ое простое число. Расчет чисел с номерами от 1000 до 10000 на Pentium, 1.7 ГГц занял 0.015 секунды (без вывода на экран или в файл)

дык кто Вам мешает копирнуть ряд сюда и помочь человеку?

[Stanislav]

В матлабе:
P=primes(n);
Здесь n - верхний предел простого числа. А можно и так:
P=primes(n)
В последнем случае n желательно взять больше 10 000 000.

И будет счастье!

[Andrew10]

дык кто Вам мешает копирнуть ряд сюда и помочь человеку?

Лови!

В файле в две колонки номер простого числа и само число. Первым простым числом считается 2.
Первые 100000 чисел.  primes.zip ( 286.71 килобайт ) Кол-во скачиваний: 220

[Krys]

Извиняюсь, если офтопик, но ещё в школе на олимпиаде по математике у нас была такая задачка: какова сумма всех простых чисел до 1000? Притом время было ограниченное. Я так до сих пор и не понял, в чём тут был подвох (простота)? Я должен был перебирать все числа до 1000? Потом тупо их просуммировать? Этих чисел судя по выданной тут таблице сотня штук - замучаешься вычислять...
Кто знает отгадку?

[exSSerge]

Извиняюсь, если офтопик, но ещё в школе на олимпиаде по математике у нас была такая задачка: какова сумма всех простых чисел до 1000? Притом время было ограниченное. Я так до сих пор и не понял, в чём тут был подвох (простота)? Я должен был перебирать все числа до 1000? Потом тупо их просуммировать? Этих чисел судя по выданной тут таблице сотня штук - замучаешься вычислять...
Кто знает отгадку?

Дык, сначала все просуммировать, а потом те, которые не простые вычесть. Причём пройтись (решетом Эратосфена) придётся только по простым числам, меньше корня из 1000, т.е. до 31.

[net]

да ладно вам
в известной книге приведена очень простая формула простых чисел
2*n+1 и это известно всем
для примера по формуле 1,3,5,7, правда 9 досадное недорузумение - зато 11 и 13 последовательно потдверждают эту формулу - ну а дальше дело за мат индукцией

[Krys]

exSSerge, не очень Вас понял. Нельзя ли прямо на примере показать?
Ещё раз хочу сказать, что задача должна быть решена в ограниченное время школьником, а не знатаком высшей математики и не гением, могущим безошибочно сложить под сотню чисел :))

[pdk]

всегото одна строчка в Maple:
writedata("c:\\prime.txt",[[i,ithprime(i)]$i=1..10000]);

1 2
2 3
3 5
.......
.......

Сообщение отредактировал pdk - Oct 31 2006, 07:57

[BEZU]

2*n+1

Это формула нечетных чисел. И без досадных недоразумений =)

[net]

2*n+1

Это формула нечетных чисел. И без досадных недоразумений =)

эх молодеж и подростки - не читали вы книг ФИЗИКИ ШУТЯТ и ФИЗИКИ ПРОДОЛЖАЮТ ШУТИТЬ
очень занимательные книги - если найдете то почитайте

[BEZU]

Не читали...
Каюсь! судя по всему, сглупил... =)

[SKov]

exSSerge, не очень Вас понял. Нельзя ли прямо на примере показать?
Ещё раз хочу сказать, что задача должна быть решена в ограниченное время школьником, а не знатаком высшей математики и не гением, могущим безошибочно сложить под сотню чисел )

Думаю, мысль уважаемого exSSerge предельно ясна. Попробую ее расшифровать
и перевести на "школьный" язык
1) Считаем S= сумму ВСЕХ чисел до 1000.
Теперь из нее надо вычесть все непростые числа. В школе учат, что непростые числа должны раскладываться на сомножители.
2) Рассмотрим непростые числа до 1000, которые имеют в разложении на простые числа число 2 в качестве сомножителя. Какие это числа и сколько их? Очевидно что максимальное число это 2*500.
Любое число вида 2*Т, где Т<=500 должно быть вычтено. Т.е. складываем ВСЕ числа от 2 * 2 до 2*500 или, что то же самое , считаем сумму всех чисел от 2 до 500 и умножаем на два. Вычитаем результат из S.
3) Повторяем аналогичную процедуру для 3. Т.е. считаем сумму всех чисел от 3 до 1000/3=333, умножаем на 3 и вычитаем из результата п.2
4) Число 4 не рассматриваем, т.к. все непростые числа, делящиеся на 4 уже учтены в п.2
В этот момент становится ясно, что надо рассматривать только простые сомножители, а их не так много.
Последний пункт будет иметь номер 31. На последнем шаге надо взять сумму всех чисел от 31 до 1000/31 и умножить на 31.

[Oldring]

exSSerge, не очень Вас понял. Нельзя ли прямо на примере показать?
Ещё раз хочу сказать, что задача должна быть решена в ограниченное время школьником, а не знатаком высшей математики и не гением, могущим безошибочно сложить под сотню чисел )

Думаю, мысль уважаемого exSSerge предельно ясна. Попробую ее расшифровать
и перевести на "школьный" язык
1) Считаем S= сумму ВСЕХ чисел до 1000.
Теперь из нее надо вычесть все непростые числа. В школе учат, что непростые числа должны раскладываться на сомножители.
2) Рассмотрим непростые числа до 1000, которые имеют в разложении на простые числа число 2 в качестве сомножителя. Какие это числа и сколько их? Очевидно что максимальное число это 2*500.
Любое число вида 2*Т, где Т<=500 должно быть вычтено. Т.е. складываем ВСЕ числа от 2 * 2 до 2*500 или, что то же самое , считаем сумму всех чисел от 2 до 500 и умножаем на два. Вычитаем результат из S.
3) Повторяем аналогичную процедуру для 3. Т.е. считаем сумму всех чисел от 3 до 1000/3=333, умножаем на 3 и вычитаем из результата п.2
4) Число 4 не рассматриваем, т.к. все непростые числа, делящиеся на 4 уже учтены в п.2
В этот момент становится ясно, что надо рассматривать только простые сомножители, а их не так много.
Последний пункт будет иметь номер 31. На последнем шаге надо взять сумму всех чисел от 31 до 1000/31 и умножить на 31.

В этом описании есть пара проколов, то есть, это еще не решение задачи - но идея вероятно правильная. Проколы - не нужно вычитать сами простые числа (т. е. сумма для числа 3 должна быть не от 3, а от 9) и нужно еще прибавить суммы кратных парам различных простых и вычесть суммы кратных тройкам различных простых. Простое число 2 лучше обработать специально, суммируя только нечетные простые. В общем, повозиться нужно - но проде все в пределах возможностей школьника.

[SKov]

exSSerge, не очень Вас понял. Нельзя ли прямо на примере показать?
Ещё раз хочу сказать, что задача должна быть решена в ограниченное время школьником, а не знатаком высшей математики и не гением, могущим безошибочно сложить под сотню чисел )

Думаю, мысль уважаемого exSSerge предельно ясна. Попробую ее расшифровать
и перевести на "школьный" язык
1) Считаем S= сумму ВСЕХ чисел до 1000.
Теперь из нее надо вычесть все непростые числа. В школе учат, что непростые числа должны раскладываться на сомножители.
2) Рассмотрим непростые числа до 1000, которые имеют в разложении на простые числа число 2 в качестве сомножителя. Какие это числа и сколько их? Очевидно что максимальное число это 2*500.
Любое число вида 2*Т, где Т<=500 должно быть вычтено. Т.е. складываем ВСЕ числа от 2 * 2 до 2*500 или, что то же самое , считаем сумму всех чисел от 2 до 500 и умножаем на два. Вычитаем результат из S.
3) Повторяем аналогичную процедуру для 3. Т.е. считаем сумму всех чисел от 3 до 1000/3=333, умножаем на 3 и вычитаем из результата п.2
4) Число 4 не рассматриваем, т.к. все непростые числа, делящиеся на 4 уже учтены в п.2
В этот момент становится ясно, что надо рассматривать только простые сомножители, а их не так много.
Последний пункт будет иметь номер 31. На последнем шаге надо взять сумму всех чисел от 31 до 1000/31 и умножить на 31.

В этом описании есть пара проколов, то есть, это еще не решение задачи - но идея вероятно правильная. Проколы - не нужно вычитать сами простые числа (т. е. сумма для числа 3 должна быть не от 3, а от 9) и нужно еще прибавить суммы кратных парам различных простых и вычесть суммы кратных тройкам различных простых. Простое число 2 лучше обработать специально, суммируя только нечетные простые. В общем, повозиться нужно - но проде все в пределах возможностей школьника.

Не во всем согласен с уважаемый Oldring
По пунктам:
1)"не нужно вычитать сами простые числа (т. е. сумма для числа 3 должна быть не от 3, а от 9)"
Никто и не собирался этого делать. В моем п.2 четко записано: " складываем ВСЕ числа от 2 * 2 до 2*500 ". Видите, здесь считается сумма не от 2 а от 2*2. Просто удобнее вынести 2 за скобки, подсчитать сумму в скобках и один раз умножить на 2. Аналогично - с другими простыми числами.
2)"нужно еще прибавить суммы кратных парам различных простых и вычесть суммы кратных тройкам различных простых." Тут есть разумное зерно. Действительно, если число делится и на 2 и на 3 (например, 2*3*6=36),то мы его выбросим два раза (2*18 и 3*12). В чуть более общем виде: если число содержит несколько простых сомножителей, то оно будет вычтено столько раз, сколько (разных)простых сомножителей в него входит. Как это просто учесть (без тупого перебора пар, троек и т.д.) - я сразу не могу сообразить . надо представить себя школьником и подумать
С уважением,
SKov

[exSSerge]

В чуть более общем виде: если число содержит несколько простых сомножителей, то оно будет вычтено столько раз, сколько (разных)простых сомножителей в него входит. Как это просто учесть (без тупого перебора пар, троек и т.д.) - я сразу не могу сообразить . надо представить себя школьником и подумать

Вот и мне, когда писал, показалось что нашёл способ это сделать.
Потом подумал - оказалось ошибался.
Можно попробовать тем-же методом подсчитывать сумму непростых чисел уже учтённых на прошлых шагах, но получается уж очень развесистый рекурсивный алгоритм. Крыша уже поскрипывает, того и гляди - поедет.

[Oldring]

В чуть более общем виде: если число содержит несколько простых сомножителей, то оно будет вычтено столько раз, сколько (разных)простых сомножителей в него входит. Как это просто учесть (без тупого перебора пар, троек и т.д.) - я сразу не могу сообразить . надо представить себя школьником и подумать

Вот и мне, когда писал, показалось что нашёл способ это сделать.
Потом подумал - оказалось ошибался.
Можно попробовать тем-же методом подсчитывать сумму непростых чисел уже учтённых на прошлых шагах, но получается уж очень развесистый рекурсивный алгоритм. Крыша уже поскрипывает, того и гляди - поедет.

Да не такой уж и долгий тупой перебор.
Если забыть про четные с самого начала - четверок нет совсем, а троек всего три. Ну а пар оказывается 45 Не дюжина конечно - но и не несколько сотен уже.

[UMP]

 e10_06Dyak.rar ( 2.64 килобайт ) Кол-во скачиваний: 143
В книге Дьяконов В.П. Энциклопедия Mathcad 200i, 11 М.: Солон-Пресс, 2004 приведена прикрепленный к настоящему сообщению файл, предназначенный для вычисления про-стых числ.

[-=ВН=-]

Подскажите, где можно найти ряд простых чисел. От 1000 и дальше. Поиском найти не смог.

Если файл прицепится, то в нем.
Когда-то генерировал для своих нужд. До миллиона с чем-то. Первый столбуц - порядковый номер.

Прикрепленные файлы

 SN131072.rar ( 494.79 килобайт ) Кол-во скачиваний: 41

 

[-=ВН=-]

exSSerge, не очень Вас понял. Нельзя ли прямо на примере показать?
Ещё раз хочу сказать, что задача должна быть решена в ограниченное время школьником, а не знатаком высшей математики и не гением, могущим безошибочно сложить под сотню чисел )

Думаю, мысль уважаемого exSSerge предельно ясна. Попробую ее расшифровать
и перевести на "школьный" язык
1) Считаем S= сумму ВСЕХ чисел до 1000.
Теперь из нее надо вычесть все непростые числа. В школе учат, что непростые числа должны раскладываться на сомножители.
2) Рассмотрим непростые числа до 1000, которые имеют в разложении на простые числа число 2 в качестве сомножителя. Какие это числа и сколько их? Очевидно что максимальное число это 2*500.
Любое число вида 2*Т, где Т<=500 должно быть вычтено. Т.е. складываем ВСЕ числа от 2 * 2 до 2*500 или, что то же самое , считаем сумму всех чисел от 2 до 500 и умножаем на два. Вычитаем результат из S.
3) Повторяем аналогичную процедуру для 3. Т.е. считаем сумму всех чисел от 3 до 1000/3=333, умножаем на 3 и вычитаем из результата п.2
4) Число 4 не рассматриваем, т.к. все непростые числа, делящиеся на 4 уже учтены в п.2
В этот момент становится ясно, что надо рассматривать только простые сомножители, а их не так много.
Последний пункт будет иметь номер 31. На последнем шаге надо взять сумму всех чисел от 31 до 1000/31 и умножить на 31.

Что-то похожее...
1. Считаем сумму всех нечетных чисел, от 1. Ар. прогрессия. Сумма=1000*250. Прибавлеякм к ней 2. Итого S1=250002
2. Считаем сумму всех чисел, делящихся на 5, соотвенно на 5 и оканивающихся.
В каждом десятке одно такое число. Десятков 100. Итого 100 чисел. Ар прогрессия. Сумма=1000*50.
Вычитаем ее из S1 и прибавляем 5. Итого S2=200007.
3a. Считаем сумму всех, кончающихся на 1 и делящихся на 3.
Ряд этих чисел образует арифм. прогрессию с начальным числом 21, интервалом 30 и последним числом 981. Итого 33 числа. Сумма,S3a=21+1002*16.
3b. сумму всех чисел, кончающихся на 3 и делящихся на 3, исключая само число 3.
Опять прогрессия из 33 чисел с шагом 30. Начало=33, конец 993. Сумма, S3b=33+1026*16
3c. Сумму, кончающихся на 7 и делящихся на 3. Начало прогрессии=27, конец=987, интервал=30.
33 числа. S3с=27+1014*16
3d. Кончаются на 9, делятся на 3. Началопрогрессии=9, конец=999, интервал=30, 34 числа.
S3d=9+39+1068*16.
S3=S2-(S3a+S3b+S3c+S3d)=200007-129-4110*16.
4. Осталось 8 чисел, на которые может разлагаться любое составное число из осташихся.
7,11,13,17,19,23,29,31.
7 стоит особняком. Так как оно моожет входить в тройные произведения.
Числа 11,13,17,19,23,29,31 могут образовывать только 2-ные произведения.
Произведений этих 28, считаются и суммируются врукопашную. Это будет S4a.
Число 7 образует еще ряд составных чисел:
7*7; 7*11; 7*13;7*17;7*19;7*23;7*29;7*31;
7*7*7; 7*7*11;7*7*13;7*7*17;7*7*19;
7*11*11;
Их сумма S4b.
Итого сумма всех простых, от 1 до 1000, включая 1 S=200007-129-4110*16-S4a-S4b.

[-=ВН=-]

exSSerge, не очень Вас понял. Нельзя ли прямо на примере показать?
Ещё раз хочу сказать, что задача должна быть решена в ограниченное время школьником, а не знатаком высшей математики и не гением, могущим безошибочно сложить под сотню чисел )

Думаю, мысль уважаемого exSSerge предельно ясна. Попробую ее расшифровать
и перевести на "школьный" язык
1) Считаем S= сумму ВСЕХ чисел до 1000.
Теперь из нее надо вычесть все непростые числа. В школе учат, что непростые числа должны раскладываться на сомножители.
2) Рассмотрим непростые числа до 1000, которые имеют в разложении на простые числа число 2 в качестве сомножителя. Какие это числа и сколько их? Очевидно что максимальное число это 2*500.
Любое число вида 2*Т, где Т<=500 должно быть вычтено. Т.е. складываем ВСЕ числа от 2 * 2 до 2*500 или, что то же самое , считаем сумму всех чисел от 2 до 500 и умножаем на два. Вычитаем результат из S.
3) Повторяем аналогичную процедуру для 3. Т.е. считаем сумму всех чисел от 3 до 1000/3=333, умножаем на 3 и вычитаем из результата п.2
4) Число 4 не рассматриваем, т.к. все непростые числа, делящиеся на 4 уже учтены в п.2
В этот момент становится ясно, что надо рассматривать только простые сомножители, а их не так много.
Последний пункт будет иметь номер 31. На последнем шаге надо взять сумму всех чисел от 31 до 1000/31 и умножить на 31.

Что-то похожее...
1. Считаем сумму всех нечетных чисел, от 1. Ар. прогрессия. Сумма=1000*250. Прибавлеякм к ней 2. Итого S1=250002
2. Считаем сумму всех чисел, делящихся на 5, соотвенно на 5 и оканивающихся.
В каждом десятке одно такое число. Десятков 100. Итого 100 чисел. Ар прогрессия. Сумма=1000*50.
Вычитаем ее из S1 и прибавляем 5. Итого S2=200007.
3a. Считаем сумму всех, кончающихся на 1 и делящихся на 3.
Ряд этих чисел образует арифм. прогрессию с начальным числом 21, интервалом 30 и последним числом 981. Итого 33 числа. Сумма,S3a=21+1002*16.
3b. сумму всех чисел, кончающихся на 3 и делящихся на 3, исключая само число 3.
Опять прогрессия из 33 чисел с шагом 30. Начало=33, конец 993. Сумма, S3b=33+1026*16
3c. Сумму, кончающихся на 7 и делящихся на 3. Начало прогрессии=27, конец=987, интервал=30.
33 числа. S3с=27+1014*16
3d. Кончаются на 9, делятся на 3. Началопрогрессии=9, конец=999, интервал=30, 34 числа.
S3d=9+39+1068*16.
S3=S2-(S3a+S3b+S3c+S3d)=200007-129-4110*16.
4. Осталось 8 чисел, на которые может разлагаться любое составное число из осташихся.
7,11,13,17,19,23,29,31.
7 стоит особняком. Так как оно моожет входить в тройные произведения.
Числа 11,13,17,19,23,29,31 могут образовывать только 2-ные произведения.
Произведений этих 28, считаются и суммируются врукопашную. Это будет S4a.
Число 7 образует еще ряд составных чисел:
7*7; 7*11; 7*13;7*17;7*19;7*23;7*29;7*31;
7*7*7; 7*7*11;7*7*13;7*7*17;7*7*19;
7*11*11;
Их сумма S4b.
Итого сумма всех простых, от 1 до 1000, включая 1 S=200007-129-4110*16-S4a-S4b.

В 4 пункте незадача случилась. Пардон.