Finding Prime number - Programmers Heaven

Howdy, Stranger!

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

Categories

Finding Prime number

Chandan ThourChandan Thour 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

Comments

  • antonsantons 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.
  • IDKIDK 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]

  • BitByBit_ThorBitByBit_Thor 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



Sign In or Register to comment.