Geek Answers Handbook

The best way to find a prime

which would be the best way to find a prime so that the time complexity is significantly reduced.

+5
source share
9 answers

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 complexity O ((n log n) (log log n)). Atkin sieve has O (N / log log n) complexity.

If you have a number and want to know if it is simple, this is called running a primality test . The naive approach is to check all numbers m from 2 to sqrt (n) and check that n% m is not 0. If you want to expand this a bit, you can throw out all the even numbers (except 2). There are also some other improvements to this naive approach that can improve performance, as well as other, more advanced methods.

+42
source

Use the Eratosthenes sieve if you want to list primes. If you want to generate a large prime, generate a random odd number and check for simplicity .

+17
source

, . , .

, 10 000 000 000 http://www.prime-numbers.org/

+13

xkcd:

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

1 , , , , , , , 3 000 000 - ( , VB.net), . ++ 5-20 .

+3

, - - .

+1

:

1) if a number - ? , 2000 ;)

2) the prime numbers N?

, , . Sieve of Atkin . N . . :

EDIT: @avakar

, , , AKS - ! :

. AKS , A , a n .

+1

, . OpenSSL GNU MP.

0

. , ... .

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]);
        }            
    }
}
-2

More articles:


All Articles