What is the best way to find a prime number?

Question

what will be the best way to find a prime number so that the time complexity is much reduced.

Answer 1

When it comes to finding prime numbers, the Sieve of Eratosthenes and the Sieve of Atkin are two possible solutions. The Sieve of Eratosthenes has a complexity of O((n log n)(log log n)). The Sieve of Atkin has a complexity of O(N / log log n).

If you have a number and you want to find out if it's prime, that is called performing a primality test. The naive approach is to check all numbers m from 2 to sqrt(n) and verify that n % m is not 0. If you want to expand this slightly, you can throw out all even numbers (except 2). There are also some other enhancements to this naive approach that might improve performance, along with other, more advanced techniques.

Answer 2

Use sieve of Eratosthenes is if you want to enumerate primes. If you want to generate a large prime, generate a random odd number and check for primality.

Answer 3

If it's below a certain range, best way would be to look it up in a precomputed list. There's plenty of them, up to very high numbers.

Example, all the primes up to 10,000,000,000 at http://www.prime-numbers.org/

Answer 4

Inspired by xkcd:

int findPrimeNumber() {
    return 2; // guaranteed to be prime
}

Answer 5

If you want to generate primes from 1 to whatever, then the fastest way is probably a wheeled Sieve as implemented here, which can typically test more than 3,000,000 candidate primes a second on an average laptop (and that's using an unoptimized language like VB.net), and factor the non-primes to boot. In c++ it could be easily 5 to 20 times faster.

Answer 6

Although there are more efficient algorithms, the Miller-Rabin primality test is one of the simplest tests to implement.

Answer 7

There are two different questions:

1) How to find if a number is a prime number? If you discover an efficient algorithm for this one, you will be famous for the next 2000 years ;)

2) How to find the prime numbers up to a limit N?

probably this is what you are asking about. Sieve of Atkin is the most efficient one If your range or limit N is really big number. In reasonable ranges, you could implement an optimized variation of Sieve of Eratosthenes. I found these two sites to be more than useful:

• The Black Key Sieve
• The Sieve of Eratosthenes

EDIT: @avakar

While I am more than beginner on the subject, I don't think AKS is the waited algorithm! From the same source:

However, some composite numbers also satisfy the equivalence. The proof of correctness for AKS consists of showing that there exists a suitably small r and suitably small set of integers A such that if the equivalence holds for all such a in A then n must be prime.

Answer 8

Take a look at existing libraries e.g. OpenSSL and GNU MP.

Answer 9

I found a way.But may its lengthy, but its perfect ..no flaws in it.

package javaapplication4;
import java.io.*;
import java.util.*;

public class Main
{ 
    static Vector vprime = new Vector();
    static Vector vnotprime = new Vector();
    static Vector newVect = new Vector(new LinkedHashSet());
    static TreeSet<Integer> st = new TreeSet<Integer>();
    static int n = 0;
    static int starr[];    

    void prime()
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number to begin");
        int beg = sc.nextInt();
        System.out.println("Enter number to end");
        int end = sc.nextInt();
        try
        {
            for (int i = beg; i <= end; i++)
            {
                if (i == 1)
                {
                    vnotprime.add(i);
                    st.add(i);
                }
                if (i == 2)
                {
                    vprime.add(i);
                }
                if (i%2 != 0 && i%(Math.sqrt(i)) != 0)
                {
                    vprime.add(i);
                }
                if (i%2 == 0 && i != 2)
                {
                    vnotprime.add(i);
                    st.add(i);
                }
                if (i%(Math.sqrt(i)) == 0)
                {
                    vnotprime.add(i);
                    st.add(i);   
                }
                /*if (i%(Math.sqrt(i)) == 0 && i != 1)
                {
                    vnotprime.add(i);
                }*/
            }
        }
        catch(Exception ex)
        {
            System.out.println("Enter proper value");
        }   
    }

    void showprime()
    {
        System.out.println("Prime Numbers are");
        Iterator it = vprime.iterator();
        while (it.hasNext())
        {
            System.out.println(it.next());
            for (int i : st)
            {    
            }
        }
    }

    void shownonprime()
    {
        System.out.println("these are non-Prime Numbers are");
        Iterator it = st.iterator();
        int len = st.size(), k = 0;
        starr = new int[len];
        while (it.hasNext())
        {
            System.out.println(it.next());
        }
        for (int i:st)
        {
            starr[k++] = i;
        }
    }

    public static void main(String[] args) throws IOException, Exception
    {
        Main m = new Main();
        m.prime();
        m.showprime();
        m.shownonprime();
        for(int i = 0; i < starr.length; i++)
        {
            System.out.println("I got it " + starr[i]);
        }            
    }
}