Finding Prime number

Chandan Thour

What is the most optimum method of finding a prime number?
Till we use a method of incrimenting a number and then dividing it with all the preceding numbers.
Kindly tell the most efficient method of finidng a prime number.
Post the code or link to it.]

Regards
chandan

antons

: What is the most optimum method of finding a prime number?
: Till we use a method of incrimenting a number and then dividing it with all the preceding numbers.
: Kindly tell the most efficient method of finidng a prime number.
: Post the code or link to it.]
:
: Regards
: chandan
:


You can at least skip every second number since it is even and not prime. If you manage to deduce a formula of which the result is always a prime number, a math institute apparently will pay you one million dollars. I cant remember their name now.

IDK

: : What is the most optimum method of finding a prime number?
: : Till we use a method of incrimenting a number and then dividing it with all the preceding numbers.
: : Kindly tell the most efficient method of finidng a prime number.
: : Post the code or link to it.]
: :
: : Regards
: : chandan
: :
:
:
: You can at least skip every second number since it is even and not prime. If you manage to deduce a formula of which the result is always a prime number, a math institute apparently will pay you one million dollars. I cant remember their name now.
:
This is one of the unsolved problems of mathematics.
One way to speed up the algorithm is to do like this:
[code]
do forever
a++
b=1
do
inc b
until b = a OR (a mod b) > 0
if b = a, it's a prime
else it's not
[/code]
Or even faster in assembler:
[code]
start:
inc ax
xor bx,bx
inc bx
loopstart:
inc bx
cmp ax,bx
je prime
mov cx,ax
mod cx,bx
jnz notprime
jmp loopstart

prime:
print "It's prime" ;OK, I don't got the time to write all the memmory.
jmp start

notprime:
print "It's not prime"
jmp start
[/code]
I wrote it in psuedo asm, I don't got time right now to write it in real asm.

[b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]

BitByBit_Thor

[b][red]This message was edited by BitByBit_Thor at 2005-8-6 9:50:48[/red][/b][hr]
To speed it up a bit more, the following two hints:
1. To check if a number is prime you only need to divide it by 2 to the square root of that number, including the square root.
2. Actually, but this is only faster if you're creating a row of primes, you only need to try and divide the number by every prime number that is between 2 and it's square root. But like I said, for a single number this is rarely faster.

And another remark:
For checking a row of number for primality, you could also use "The Sieve of Erasthotenes". Might be worth checking out if you're interested ;-)

Greets...
Richard