Полная версия этой страницы: Простые числа
Форум разработчиков электроники ELECTRONIX.ru > Cистемный уровень проектирования > Математика и Физика
Подскажите, где можно найти ряд простых чисел. От 1000 и дальше. Поиском найти не смог.
Цитата(ig_z @ Oct 2 2006, 15:21) 
Подскажите, где можно найти ряд простых чисел. От 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;
}
}
}
//
// 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.: Кстати, о формуле простых чисел (
), вот человек получил кое какие аппроксимации ряда (я сам не проверял, т.к. довольно холоден к фундаментальной математике). Но если надумаете, как их применить в прикладных задачах - Вам и карты в руки... 
Цитата(DRUID3 @ Oct 2 2006, 16:21)
Цитата(ig_z @ Oct 2 2006, 15:21)
Подскажите, где можно найти ряд простых чисел. От 1000 и дальше. Поиском найти не смог.
Вы бы еще формулу попросили...Спасибо за ответ. Я еще более холоден к данной теме. Просто просьба со стороны.
Что касается формульного расчета, то действительно гарантировано простое число на выходе. Но, если я не ошибаюсь, нет гарантии, что будет рассчитан весь ряд без пропусков. Вроде я слышал, что раньше публиковали полные ряды, получаемые тупым перебором. Вот такое бы найти.
В Mathematica-5.2 функция Prime[n] дает n-ое простое число. Расчет чисел с номерами от 1000 до 10000 на Pentium, 1.7 ГГц занял 0.015 секунды (без вывода на экран или в файл)
Цитата(Andrew10 @ Oct 2 2006, 17:35)
В Mathematica-5.2 функция Prime[n] дает n-ое простое число. Расчет чисел с номерами от 1000 до 10000 на Pentium, 1.7 ГГц занял 0.015 секунды (без вывода на экран или в файл)
дык кто Вам мешает копирнуть ряд сюда и помочь человеку?
В матлабе:
P=primes(n);
Здесь n - верхний предел простого числа. А можно и так:
P=primes(n)
В последнем случае n желательно взять больше 10 000 000.
И будет счастье!
P=primes(n);
Здесь n - верхний предел простого числа. А можно и так:
P=primes(n)
В последнем случае n желательно взять больше 10 000 000.
И будет счастье!
Цитата
дык кто Вам мешает копирнуть ряд сюда и помочь человеку?Лови!
В файле в две колонки номер простого числа и само число. Первым простым числом считается 2.
Первые 100000 чисел.Нажмите для просмотра прикрепленного файла
Извиняюсь, если офтопик, но ещё в школе на олимпиаде по математике у нас была такая задачка: какова сумма всех простых чисел до 1000? Притом время было ограниченное. Я так до сих пор и не понял, в чём тут был подвох (простота)? Я должен был перебирать все числа до 1000? Потом тупо их просуммировать? Этих чисел судя по выданной тут таблице сотня штук - замучаешься вычислять...
Кто знает отгадку?
Кто знает отгадку?
Цитата(Krys @ Oct 27 2006, 15:08)
Извиняюсь, если офтопик, но ещё в школе на олимпиаде по математике у нас была такая задачка: какова сумма всех простых чисел до 1000? Притом время было ограниченное. Я так до сих пор и не понял, в чём тут был подвох (простота)? Я должен был перебирать все числа до 1000? Потом тупо их просуммировать? Этих чисел судя по выданной тут таблице сотня штук - замучаешься вычислять...
Кто знает отгадку?
Кто знает отгадку?
Дык, сначала все просуммировать, а потом те, которые не простые вычесть. Причём пройтись (решетом Эратосфена) придётся только по простым числам, меньше корня из 1000, т.е. до 31.
да ладно вам 
в известной книге приведена очень простая формула простых чисел
2*n+1 и это известно всем
для примера по формуле 1,3,5,7, правда 9 досадное недорузумение - зато 11 и 13 последовательно потдверждают эту формулу - ну а дальше дело за мат индукцией
в известной книге приведена очень простая формула простых чисел
2*n+1 и это известно всем
для примера по формуле 1,3,5,7, правда 9 досадное недорузумение - зато 11 и 13 последовательно потдверждают эту формулу - ну а дальше дело за мат индукцией
exSSerge, не очень Вас понял. Нельзя ли прямо на примере показать?
Ещё раз хочу сказать, что задача должна быть решена в ограниченное время школьником, а не знатаком высшей математики и не гением, могущим безошибочно сложить под сотню чисел :))
Ещё раз хочу сказать, что задача должна быть решена в ограниченное время школьником, а не знатаком высшей математики и не гением, могущим безошибочно сложить под сотню чисел :))
всегото одна строчка в Maple:
writedata("c:\\prime.txt",[[i,ithprime(i)]$i=1..10000]);
writedata("c:\\prime.txt",[[i,ithprime(i)]$i=1..10000]);
Цитата
1 2
2 3
3 5
.......
.......
2 3
3 5
.......
.......
Цитата(net @ Oct 27 2006, 23:11)
2*n+1
Это формула нечетных чисел. И без досадных недоразумений =)
Цитата(BEZU @ Oct 31 2006, 12:43)
Цитата(net @ Oct 27 2006, 23:11)
2*n+1
Это формула нечетных чисел. И без досадных недоразумений =)
эх молодеж и подростки - не читали вы книг ФИЗИКИ ШУТЯТ и ФИЗИКИ ПРОДОЛЖАЮТ ШУТИТЬ
очень занимательные книги - если найдете то почитайте
Не читали...
Каюсь! судя по всему, сглупил... =)
Каюсь! судя по всему, сглупил... =)
Цитата(Krys @ Oct 28 2006, 10:19)
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.
Цитата(SKov @ Nov 1 2006, 17:22)
Цитата(Krys @ Oct 28 2006, 10:19)
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 @ Nov 1 2006, 17:51)
Цитата(SKov @ Nov 1 2006, 17:22)
Цитата(Krys @ Oct 28 2006, 10:19)
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
Цитата(SKov @ Nov 2 2006, 13:49)
В чуть более общем виде: если число содержит несколько простых сомножителей, то оно будет вычтено столько раз, сколько (разных)простых сомножителей в него входит. Как это просто учесть (без тупого перебора пар, троек и т.д.) - я сразу не могу сообразить . надо представить себя школьником и подумать
Вот и мне, когда писал, показалось что нашёл способ это сделать.
Потом подумал - оказалось ошибался.
Можно попробовать тем-же методом подсчитывать сумму непростых чисел уже учтённых на прошлых шагах, но получается уж очень развесистый рекурсивный алгоритм. Крыша уже поскрипывает, того и гляди - поедет.
Цитата(exSSerge @ Nov 2 2006, 12:24)
Цитата(SKov @ Nov 2 2006, 13:49)
В чуть более общем виде: если число содержит несколько простых сомножителей, то оно будет вычтено столько раз, сколько (разных)простых сомножителей в него входит. Как это просто учесть (без тупого перебора пар, троек и т.д.) - я сразу не могу сообразить . надо представить себя школьником и подумать
Вот и мне, когда писал, показалось что нашёл способ это сделать.
Потом подумал - оказалось ошибался.
Можно попробовать тем-же методом подсчитывать сумму непростых чисел уже учтённых на прошлых шагах, но получается уж очень развесистый рекурсивный алгоритм. Крыша уже поскрипывает, того и гляди - поедет.
Да не такой уж и долгий тупой перебор.
Если забыть про четные с самого начала - четверок нет совсем, а троек всего три. Ну а пар оказывается 45
Не дюжина конечно - но и не несколько сотен уже.
Нажмите для просмотра прикрепленного файлаВ книге Дьяконов В.П. Энциклопедия Mathcad 200i, 11 М.: Солон-Пресс, 2004 приведена прикрепленный к настоящему сообщению файл, предназначенный для вычисления про-стых числ.
Цитата(ig_z @ Oct 2 2006, 15:21)
Подскажите, где можно найти ряд простых чисел. От 1000 и дальше. Поиском найти не смог.
Если файл прицепится, то в нем.
Когда-то генерировал для своих нужд. До миллиона с чем-то. Первый столбуц - порядковый номер.
Цитата(SKov @ Nov 1 2006, 17:22)
Цитата(Krys @ Oct 28 2006, 10:19)
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.
Цитата(-=ВН=- @ Nov 3 2006, 12:05)
Цитата(SKov @ Nov 1 2006, 17:22)
Цитата(Krys @ Oct 28 2006, 10:19)
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 пункте незадача случилась. Пардон.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.