#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmers Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use it's exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

# Finding Prime number

Posts: 20Member
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
· ·

• Posts: 117Member
: 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.
· ·
• Posts: 1,784Member
: : 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]

· ·
• Posts: 2,444Member
[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

· ·