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
Comments
: 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.
: : 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]
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