The PRIME NUMBERS

[RST]

A word of clarrification....

I meant is it OK if the program skips a prime? For example, there's a few well-known algorithms that generate prime numbers, but they skip most of them. (eg: 3, 5, 11, 13.... [Skips 7])

I should point out that these algorthims are considerably faster than others.

[Touf]

Am i dreaming ???

Of course ALL prime numbers have to be found !
If any prime number is forgotten , the program won't be accepted !

But please , mail me your programs , don't show it ...

[Touf]

Short message for Mango ....

Can you please send me your e-mail and some informations about you ( see http://ToufQb.free.fr/classement.php?langue=1 )

Of course , if you don't want , don't do it :wink:

[Mango]

Short message for Mango ....

Touf, I'll be glad to send info...however, I wanted to make sure you were giving credit where it is due. The 1st program I listed is my own method...the second was conceptualized and programmed by someone else...

It is unclear from your web-site which program was used.

Also...to be fair to all the methods, they should be compiled, because interpreted qbasic slows down when comments are present, and for spaces between lines of code!!!

Cheers

[Touf]

lol
I've understood that your program was the first or the two ones !
But the program I'v tested is YOURS ...

The other-one is REALLY the BEST , but I don't manage to make it stop at a specified number ... doesn't matter ... I've no info on this programmer .

So , I won't class the second program .

:wink:

[wizardlife]

A word of clarrification....

I meant is it OK if the program skips a prime? For example, there's a few well-known algorithms that generate prime numbers, but they skip most of them. (eg: 3, 5, 11, 13.... [Skips 7])

I should point out that these algorthims are considerably faster than others.

Those break down after a point though... I read uh... some article on it once... yeah...

Are there actually algos that consistently and accurately generate primes?

[Antoni Gual]

It seems the only way to find all primes is to use the old Erathostenes's sieve. Even the second progam Mango posts is using it in a very convoluted way. The complication is to keep the primes stored in a file and only a sliding window on the sieve. The only goal of all this is to save memory, the sieve is still at the base.

This Rich Geldreich's code has been in the ABC packets since it's creation in 1995, but it mentions a 486 in the comments so I imagine the program has more than 10 years!
I have tested it, it calculates all primes up to 2 000 000 in 6 seconds, then it needs 50 seconds to display them..

[Touf]

So , Mango ?
Can I have some informations about you ? ... because NOBODY has reach your level for the moment !

( City , mail , URL ( if u have one ) ) .. you can send me these informations by mail if you want .

[Mango]

[quote="Touf"]NOBODY has reach your level for the moment !/quote]

I just looked at the code I wrote earlier...and tweaked it a bit. This one is about 75% faster. The difference is I moved a squareroot out of a loop, and I got rid of a comparison and a goto.

Code:

DEFINT A-Z           'Joe Campbell-2003
DIM smallprimes(1 TO 3500) AS INTEGER  'array holds forst 3500 prime numbers
CLS
PRINT "This program finds primes, then prints the highest found, 1 per second"
a = 0        
max = 3
smallprimes(1) = 3
next1 = 5
count = 1
DO WHILE count < 3500
sqroot = SQR(next1)
DO
  a = a + 1
  IF next1 MOD smallprimes(a) = 0 THEN GOTO notprime
LOOP WHILE sqroot > smallprimes(a)
count = count + 1
smallprimes(count) = next1
notprime:
next1 = next1 + 2
a = 0
LOOP
nextbig& = next1 - 2
over:  
t& = TIMER
t1& = t& + 1
DO
sqroot = SQR(nextbig&)
DO
a = a + 1
IF sqroot < smallprimes(a) THEN  
    APrime& = nextbig&
    EXIT DO
END IF
LOOP WHILE nextbig& MOD smallprimes(a)  
nextbig& = nextbig& + 2
a = 0  
LOOP UNTIL TIMER > t1&
LOCATE 2
PRINT APrime&
GOTO over

[Touf]

haha !
A french programer has send a faster program !

Are the French programers better than US programers ?? :???:

lol