Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Список ДОбрых Дел: Дело четвёртое (Нахождение простых чисел)
СообщениеДобавлено: 06 июл 2019, 11:02 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2019, 14:15
Сообщений: 27
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Я хочу представить новый способ нахождения простых чисел на интервале от
1 до некого N, на следующем примере найдем простые числа на интервале от 1 до 1000:
Запишем первые три нечетных числа и поставим ноль возле числа которое делится на 3:
[math]1_{1}[/math] [math]{3_0}[/math] [math]5_{1}[/math]
ноль означает что число делится на 3 без остатка
единица означает что число делится на 3 с остатком
Увеличим интервал в 5 раз и поставим ноль возле числа которое делится на 5:
[math]01_{1}[/math] [math]03_{0}[/math] [math]05_{0}[/math][math]07_{1}[/math] [math]09_{0}[/math] [math]11_{1}[/math] [math]13_{1}[/math] [math]15_{0}[/math] [math]17_{1}[/math] [math]19_{1}[/math] [math]21_{0}[/math] [math]23_{1}[/math] [math]25_{0}[/math] [math]27_{0}[/math] [math]29_{1}[/math]
ноль означает что число делится на 3 или(и) 5 без остатка
Увеличим интервал в 7 раз и поставим ноль возле числа которое делится на 7:
[math]001_{1}[/math] [math]003_{0}[/math] [math]005_{0}[/math] [math]007_{0}[/math] [math]009_{0}[/math] [math]011_{1}[/math] [math]013_{1}[/math] [math]015_{0}[/math] [math]017_{1}[/math] [math]019_{1}[/math] [math]021_{0}[/math] [math]023_{1}[/math] [math]025_{0}[/math] [math]027_{0}[/math] [math]029_{1}[/math]

[math]031_{1}[/math] [math]033_{0}[/math] [math]035_{0}[/math] [math]037_{1}[/math] [math]039_{0}[/math] [math]041_{1}[/math] [math]043_{1}[/math] [math]045_{0}[/math] [math]047_{1}[/math] [math]049_{0}[/math] [math]051_{0}[/math] [math]053_{1}[/math] [math]055_{0}[/math] [math]057_{0}[/math] [math]059_{1}[/math]

[math]061_{1}[/math] [math]063_{0}[/math] [math]065_{0}[/math] [math]067_{1}[/math] [math]069_{0}[/math] [math]071_{1}[/math] [math]073_{1}[/math] [math]075_{0}[/math] [math]077_{0}[/math] [math]079_{1}[/math] [math]081_{0}[/math] [math]083_{1}[/math] [math]085_{0}[/math] [math]087_{0}[/math] [math]089_{1}[/math]

[math]091_{0}[/math] [math]093_{0}[/math] [math]095_{0}[/math] [math]097_{1}[/math] [math]099_{0}[/math] [math]101_{1}[/math] [math]103_{1}[/math] [math]105_{0}[/math] [math]107_{1}[/math] [math]109_{1}[/math] [math]111_{0}[/math] [math]113_{1}[/math] [math]115_{0}[/math] [math]117_{0}[/math] [math]119_{0}[/math]

[math]121_{1}[/math] [math]123_{0}[/math] [math]125_{0}[/math] [math]127_{1}[/math] [math]129_{0}[/math] [math]131_{1}[/math] [math]133_{0}[/math] [math]135_{0}[/math] [math]137_{1}[/math] [math]139_{1}[/math] [math]141_{0}[/math] [math]143_{1}[/math] [math]145_{0}[/math] [math]147_{0}[/math] [math]149_{1}[/math]

[math]151_{1}[/math] [math]153_{0}[/math] [math]155_{0}[/math] [math]157_{1}[/math] [math]159_{0}[/math] [math]161_{0}[/math] [math]163_{1}[/math] [math]165_{0}[/math] [math]167_{1}[/math] [math]169_{1}[/math] [math]171_{0}[/math] [math]173_{1}[/math] [math]175_{0}[/math] [math]177_{0}[/math] [math]179_{1}[/math]

[math]181_{1}[/math] [math]183_{0}[/math] [math]185_{0}[/math] [math]187_{1}[/math] [math]189_{0}[/math] [math]191_{1}[/math] [math]193_{1}[/math] [math]195_{0}[/math] [math]197_{1}[/math] [math]199_{1}[/math] [math]201_{0}[/math] [math]203_{0}[/math] [math]205_{0}[/math] [math]207_{0}[/math] [math]209_{1}[/math]

ноль означает что число делится на 3 или(и) 5 или(и) 7 без остатка
Найдем количество чисел, которые не делятся на 3,5,7,11 (рассматриваем только нечетные числа):
500 div 105 = 4
500 mod 105=80
Посчитаем количество 1 на интервале от 1 до 209 оно равно 48
Посчитаем количество 1 на интервале от 1 до 80 оно равно 19 получаем
4*48 + 36 +3=231 - это количество нечетных чисел которые не делятся на 3,5,7, за
исключением 3,5,7.
Посчитаем количество чисел которые не делятся на 3,5,7,11 231-10=211.
20 - это количество 1 на интервале от 11 до 90.
Посчитаем количество чисел которые не делятся на 3,5,7,11,13 211-16=195.
16 - это количество 1 на интервале от 13 до 76.
Посчитаем количество чисел которые не делятся на 3,5,7,11,13,17 195-10=185.
10 - это количество 1 на интервале от 17 до 58.
Посчитаем количество чисел которые не делятся на 3,5,7,11,13,17,19 185-8=177.
8 - это количество 1 на интервале от 19 до 52.
Посчитаем количество чисел которые не делятся на 3,5,7,11,13,17,19,23 177-6=171.
6 - это количество 1 на интервале от 23 до 43.
Посчитаем количество чисел которые не делятся на 3,5,7,11,13,17,19,23,29 171-2=169.
2 - это количество 1 на интервале от 29 до 34.
Посчитаем количество чисел которые не делятся на 3,5,7,11,13,17,19,23,29,31 169-1=168.
1 - это количество 1 на интервале от 31 до 32.
С помощью этого метода компьютер (2 ядра по 2,5 ГГц ОП 3 GB) за 2 сек находит все простые числа
на интервале от 1 до 10^10.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Список ДОбрых Дел: Дело четвёртое (Нахождение простых чисел)
СообщениеДобавлено: 06 июл 2019, 13:42 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
28 апр 2016, 13:40
Сообщений: 3550
Cпасибо сказано: 5
Спасибо получено:
624 раз в 591 сообщениях
Очков репутации: 98

Добавить очки репутацииУменьшить очки репутации
Маловато будет, на до до 10^12 и наступит всеобщее счастье.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Список ДОбрых Дел: Дело четвёртое (Нахождение простых чисел)
СообщениеДобавлено: 09 июл 2019, 18:12 
Не в сети
Гений
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 659
Cпасибо сказано: 21
Спасибо получено:
105 раз в 103 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
Foka, а код программы можете привести?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Список ДОбрых Дел: Дело четвёртое (Нахождение простых чисел)
СообщениеДобавлено: 10 июл 2019, 05:59 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2019, 14:15
Сообщений: 27
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
var
u1,u2,u3,u4,u5,u6:integer;
i1,i2,i3,i4: integer;
j1,j2,j3,j4,j5,j6: integer;
y1,y2,y3,y4,y5,y6,y7,y8:integer;
k1,k2,k3: int64;
Fr, t1, t2,t3 : Int64;
Dt,dt1 : Extended;
begin
QueryPerformanceFrequency(Fr);
QueryPerformanceCounter(t1);
form1.Label1.Caption:='Вычисление начато';
for i1:=1 to 500000 do
a3[i1]:= true;
i1:=2;
repeat
i2:=i1;i3:=2*i1-1;i2:=i2+i3;
repeat
a3[i2]:=false;
i2:=i2+i3;
until i2>500000;
repeat
i1:=i1+1;
until a3[i1]= true;
until i1> 1581; {1581}
i2:=0;
for i1:=1 to 500000 do
if a3[i1] = true then
begin
i2:=i2+1;
d1[i2]:=2*i1-1;
end;
form1.Label2.Caption:=' i2 = '+inttostr(i2);
k1:=2*5000000000;
for i1:=1 to 217391304 do

a1[i1]:= true;
i1:=2;
repeat
i2:=i1;i3:=2*i1-1;
repeat
a1[i2]:=false;
i2:=i2+i3;
until i2>217391304;
repeat
i1:=i1+1;
until a3[i1]= true;
until i1> 10;
j1:=5000000000 div 4849845;
j2:=5000000000 mod 4849845;
i2:=0;
for i1:=1 to 4849845 do
i2:=i2+ord(a1[i1]);
i3:=0;
for i1:=1 to j2 do
i3:=i3+ord(a1[i1]);
i4:=j1*i2+i3;
form1.Memo1.Lines.Add('i4 = '+inttostr(i4));
j4:=217391304 mod 4849845;
j5:=217391304 div 4849845;
i3:=0;
for i1:=1 to j4 do
i3:=i3+ord(a1[i1]);
i2:=i2*j5+i3;
j3:=i2-1;
i4:=i4-i2+8;
y1:=9;
y2:=d1[y1];
y3:=(d1[y1] +1)div 2;
y4:= ((k1 div y2)+1)div 2;
y8:=y4;
y5:=0;
y6:=217391304;

repeat
y5:=y5+ord(a1[y3]);
a1[y3]:=false;
y3:=y3+y2;
until y3>y4;
y1:=y1+1;
repeat
y2:=d1[y1];
y3:=(d1[y1] +1)div 2;
y4:= ((k1 div y2)+1)div 2;
y7:=0;
for i1:= y4+1 to y8 do
y7:=y7+ord(a1[i1]);
y8:=y4;
j3:=j3-y5-y7;
i4:=i4-j3;
y5:=0;
repeat
y5:=y5+ord(a1[y3]);
a1[y3]:=false;
y3:=y3+y2;
until y3>y4;
y1:=y1+1;
until d1[y1]>2154;
QueryPerformanceCounter(t3);
j3:=j3-y5+1;
repeat
y2:=d1[y1];
y3:=(d1[y1] +1)div 2;
y4:= ((k1 div y2)+1)div 2;
y7:=0;
for i1:= y4+1 to y8 do
y7:=y7+ord(a1[i1]);
y8:=y4;
j3:=j3-y7-1;
{i2:=0;
for i1:= y3 to y4 do
i2:=i2+ord(a1[i1]);
form1.Memo1.Lines.Add('i2 = '+inttostr(i2));
form1.Memo1.Lines.Add('j3 = '+inttostr(j3));}
i4:=i4-j3;
y1:=y1+1;
until d1[y1]>100000;
form1.Memo1.Lines.Add('i4 = '+inttostr(i4));
form1.Label1.Caption:='Вычисление закончено';
QueryPerformanceCounter(t2);
Dt := (t2 - t1) / Fr;
Dt1 := (t2 - t3) / Fr;
form1.Label3.Caption:='Длительность выполнения в секундах: ' + FloatToStr(Dt);
form1.Label4.Caption:='Длительность выполнения в секундах: ' + FloatToStr(Dt1);

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Список ДОбрых Дел: Дело четвёртое (Нахождение простых чисел)
СообщениеДобавлено: 10 июл 2019, 16:29 
Не в сети
Гений
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 659
Cпасибо сказано: 21
Спасибо получено:
105 раз в 103 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
По правде говоря не совсем понял что за язык, что-то из паскалей? Массивов здесь нет? (к вопросу о размере памяти для заданных вами больших чисел). Где задается верхняя граница? Хотел сравнить со скоростью алгоритма Эратосфена, но не вышло.
ps Код лучше тегом Code обрамить.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Список ДОбрых Дел: Дело четвёртое (Нахождение простых чисел)
СообщениеДобавлено: 10 июл 2019, 16:40 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2019, 14:15
Сообщений: 27
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Язык написание программы DELPHI
Числа хранятся в виде нулей и единиц
Размер массива порядка 200 МБ

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 6 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Список ДОбрых Дел: Дело 11 (Признак делимости)

в форуме Размышления по поводу и без

Foka

1

202

31 дек 2020, 05:52

Список ДОбрых Дел: Дело 5 (Потерянные электроны)

в форуме Размышления по поводу и без

Foka

7

411

31 май 2020, 14:47

Список ДОбрых Дел: Дело 6 (Док-во гипотезы Гольдбаха)

в форуме Размышления по поводу и без

Foka

5

354

14 июн 2020, 16:49

Список ДОбрых Дел: Дело 10 (Бывает ли вечный двигатель)

в форуме Размышления по поводу и без

Foka

0

140

20 дек 2020, 06:58

Список ДОбрых Дел: Дело 7 (Скорость молекул воздуха)

в форуме Размышления по поводу и без

Foka

8

280

05 окт 2020, 10:56

Список ДОбрых Дел: Дело 8 (Составные числа Мерсенна)

в форуме Размышления по поводу и без

Foka

1

226

13 окт 2020, 19:54

Список ДОбрых дел:Дело 13 С дуру можно и RSA взломать

в форуме Размышления по поводу и без

Foka

1

185

13 дек 2022, 10:51

Список ДОбрых дел:Дело 12 Решение степенных уравнений

в форуме Размышления по поводу и без

Foka

3

274

21 ноя 2022, 14:54

Список ДОбрых Дел: Дело 9 (Теплоёмкость тела человека)

в форуме Размышления по поводу и без

Foka

2

253

12 дек 2020, 06:13

Список ДОбрых Дел: Дело второе (Куда текут реки)

в форуме Размышления по поводу и без

Foka

4

332

21 фев 2019, 06:50


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved