Author: Vincent Lejeune
Date: 12:02:58 05/26/05
Go up one level in this thread
On May 26, 2005 at 14:26:36, Vincent Lejeune wrote:
>On May 26, 2005 at 13:15:04, Dann Corbit wrote:
>
>>On May 26, 2005 at 12:02:37, Vincent Diepeveen wrote:
>>[snip]
>>>Hello, i can calculate prime numbers up to 10 million digits at my pc nearly,
>>>though not within 5 minutes.
>>
>>Less than a second, I imagine.
>>
>>>A prime number of 1051 digits is really peanuts to calculate within seconds.
>>
>>Do you mean to prove prime with APR-CL?
>>
>>>I'll have to refer to some other software mine there.
>>
>>All primes to 100 million takes about ten seconds on a single CPU machine.
>>
>>E:\tmp\ioccc>type p.c
>>#include<stdio.h>
>>#include<stdlib.h>
>>#include<string.h>
>>#include<time.h>
>>#define TEST(f,x)(*(f+(x)/16)&(1<<(((x)%16L)/2)))
>>#define SET(f,x)(*(f+(x)/16)|=1<<(((x)%16L)/2))
>>void check(int count_converted,unsigned long value,void*feld){if(
>>count_converted!=1){(void)puts("The scanf() function had an error conve\
>>rting input data.");free(feld);exit(EXIT_FAILURE);}if(value==0){(void)
>>puts("Value out of range. Assuming exit is desired.");free(feld);exit(
>>EXIT_SUCCESS);}}int main(int argc,char*argv[]){unsigned char*feld=NULL,*
>>zzz=NULL;unsigned long teste=1,max,mom,hits=1,count,alloc,s=0,e=1;time_t
>>begin;if(argc>1)max=(unsigned long)atof(argv[1])+10000;else max=
>>14010000L;zzz=feld=malloc((size_t)(alloc=(((max-=10000L)>>4)+1L)));if(
>>feld){memset(zzz,0,(size_t)alloc);printf("Searching prime numbers to : \
>>%lu\n",max);begin=time(NULL);while((teste+=2)<max)if(!TEST(feld,teste)){
>>if(++hits%100000L==0){printf(" %lu. prime numbers\n",hits);(void)fflush(
>>stdout);}for(mom=3L*teste;mom<max;mom+=teste<<1)SET(feld,mom);}printf("\
>> %lu prime numbers found in %lu secs.\n\nShow prime numbers",hits,(
>>unsigned long)(time(NULL)-begin));while(s<e){int cnt;printf("\n\nStart \
>>of Area : ");(void)fflush(stdout);cnt=scanf("%lu",&s);check(cnt,s,feld);
>>printf("End of Area : ");(void)fflush(stdout);cnt=scanf("%lu",&e);check(
>>cnt,s,feld);if(s<=2&&e>=2)printf("%lu\t",2L);count=s-2;if(s%2==0)count++
>>;while((count+=2)<e)if(!TEST(feld,count)&#38;&#38;count!=1)printf("%lu\t",count)
>>;}free(feld);}else{(void)puts("Memory allocation failure.");exit(
>>EXIT_FAILURE);}return 0;}
>>
>>E:\tmp\ioccc>p 100000000
>>Searching prime numbers to : 100000000
>> 100000. prime numbers
>> 200000. prime numbers
>> 300000. prime numbers
>> 400000. prime numbers
>> 500000. prime numbers
>> 600000. prime numbers
>> 700000. prime numbers
>> 800000. prime numbers
>> 900000. prime numbers
>> 1000000. prime numbers
>> 1100000. prime numbers
>> 1200000. prime numbers
>> 1300000. prime numbers
>> 1400000. prime numbers
>> 1500000. prime numbers
>> 1600000. prime numbers
>> 1700000. prime numbers
>> 1800000. prime numbers
>> 1900000. prime numbers
>> 2000000. prime numbers
>> 2100000. prime numbers
>> 2200000. prime numbers
>> 2300000. prime numbers
>> 2400000. prime numbers
>> 2500000. prime numbers
>> 2600000. prime numbers
>> 2700000. prime numbers
>> 2800000. prime numbers
>> 2900000. prime numbers
>> 3000000. prime numbers
>> 3100000. prime numbers
>> 3200000. prime numbers
>> 3300000. prime numbers
>> 3400000. prime numbers
>> 3500000. prime numbers
>> 3600000. prime numbers
>> 3700000. prime numbers
>> 3800000. prime numbers
>> 3900000. prime numbers
>> 4000000. prime numbers
>> 4100000. prime numbers
>> 4200000. prime numbers
>> 4300000. prime numbers
>> 4400000. prime numbers
>> 4500000. prime numbers
>> 4600000. prime numbers
>> 4700000. prime numbers
>> 4800000. prime numbers
>> 4900000. prime numbers
>> 5000000. prime numbers
>> 5100000. prime numbers
>> 5200000. prime numbers
>> 5300000. prime numbers
>> 5400000. prime numbers
>> 5500000. prime numbers
>> 5600000. prime numbers
>> 5700000. prime numbers
>> 5761455 prime numbers found in 10 secs.
>>
>>Show prime numbers
>>
>>Start of Area : 1234567
>>End of Area : 1234789
>>1234577 1234603 1234613 1234627 1234657 1234687 1234703 1234721 1234747 1234757
>>1234759 1234769 1234777 1234787
>>
>>Start of Area : -1
>>End of Area : -1
>
>
>I ran my old Pascal program with a bit optimize search : test division only with
>all previous prime <= sqrt(candidate)
>
>in less than 0.5 sec it give the same list as you but they're 95361th prime to
>95376th prime (not 100 millions)
>
>1234577(95361)
>1234603(95362)
>1234613(95363)
>1234627(95364)
>1234657(95365)
>1234687(95366)
>1234703(95367)
>1234721(95368)
>1234747(95369)
>1234757(95370)
>1234759(95371)
>1234769(95372)
>1234777(95373)
>1234787(95374)
>1234789(95375)
>1234799(95376)
>
>Free Pascal is free of charge : http://www.freepascal.org/
>
>source :
>----------------------------
>program nbr_prem;
>
>uses crt;
>
>var np: array [1..999999] of longint;
> ntest,n,nbr,s:longint;
> d:extended;
>
>begin
>clrscr;
>np[1]:=2;
>np[2]:=3;
>n:=2;
>nbr:=np[n];
>repeat
> nbr:=nbr+2;
> ntest:=0;
> s:=trunc(sqrt(nbr));
> repeat ntest:=ntest+1;
> d:=(nbr/np[ntest])
> until ((d=trunc(d)) or (np[ntest]>s));
> if np[ntest]>sqrt(nbr)
> then begin n:=n+1;
> np[n]:=nbr;
> if (nbr > 1234567) then writeln(nbr,'(',n,') ');
> end;
> until (nbr>=1234800);
>
>end.
>----------------------------
10 min 35 sec (on amd@2.16 Ghz) with the same simple algo to find the first 10
million prime numbers (but there's much more clever methods to prove primality
of big numbers)
15485863 (1000000th)
32452843 (2000000th)
49979687 (3000000th)
67867967 (4000000th)
86028121 (5000000th)
104395301 (6000000th)
122949823 (7000000th)
141650939 (8000000th)
160481183 (9000000th)
179424673 (10000000th)
--------------
program nbr_prem;
uses crt;
var np: array [1..99999] of longint;
ntest,n,nbr,s:longint;
d:extended;
begin
clrscr;
np[1]:=2;
np[2]:=3;
n:=2;
nbr:=np[n];
repeat
nbr:=nbr+2;
ntest:=0;
s:=trunc(sqrt(nbr));
repeat ntest:=ntest+1;
d:=(nbr/np[ntest])
until ((d=trunc(d)) or (np[ntest]>s));
if np[ntest]>sqrt(nbr)
then begin n:=n+1;
if n<99999 then np[n]:=nbr;
if (n mod 1000000 = 0) then writeln(nbr,' (',n,'th) ');
end;
until (n>=10000000);
end.
-----------------
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.