## C and C++

Moderators: None (Apply to moderate this forum)
Number of threads: 28630
Number of posts: 94612

This Forum Only

Finding Prime number Posted by Chandan Thour on 5 Aug 2005 at 10:33 PM
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
Re: Finding Prime number Posted by antons on 5 Aug 2005 at 11:42 PM
: 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.
Re: Finding Prime number Posted by IDK on 6 Aug 2005 at 3:46 AM
: : 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

Re: Finding Prime number Posted by BitByBit_Thor on 6 Aug 2005 at 9:50 AM
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

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic