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

Welcome to the new platform of Programmer's 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 its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.