Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 6 ] |
|
Автор | Сообщение | |
---|---|---|
Foka |
|
|
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. |
||
Вернуться к началу | ||
slava_psk |
|
|
Маловато будет, на до до 10^12 и наступит всеобщее счастье.
|
||
Вернуться к началу | ||
Emphatic18 |
|
|
Foka, а код программы можете привести?
|
||
Вернуться к началу | ||
Foka |
|
|
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); |
||
Вернуться к началу | ||
Emphatic18 |
|
|
По правде говоря не совсем понял что за язык, что-то из паскалей? Массивов здесь нет? (к вопросу о размере памяти для заданных вами больших чисел). Где задается верхняя граница? Хотел сравнить со скоростью алгоритма Эратосфена, но не вышло.
ps Код лучше тегом Code обрамить. |
||
Вернуться к началу | ||
Foka |
|
|
Язык написание программы DELPHI
Числа хранятся в виде нулей и единиц Размер массива порядка 200 МБ |
||
Вернуться к началу | ||
[ Сообщений: 6 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |