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

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

: : 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:

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

Or even faster in assembler:

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

I wrote it in psuedo asm, I don't got time right now to write it in real asm.

Niklas Ulvinge aka IDK

This message was edited by BitByBit_Thor at 2005-8-6 9:50:48

---

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