Что лучший способ состоит в том, чтобы найти простым числом? [закрытый]

Используйте сито Эратосфена , если вы хотите перечислить простые числа. Если вы хотите сгенерировать большое простое число, сгенерируйте случайное нечетное число и проверьте простоту .

Если он ниже определенного диапазона, лучше всего найти его в предварительно вычисленном списке. Их много, вплоть до очень больших чисел.

Например, все простые числа до 10 000 000 000 на http://www.prime-numbers.org/

На основе xkcd :

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

Если вы хотите сгенерировать простые числа от 1 до любого другого, то самым быстрым способом, вероятно, будет сито с колесами, реализованное здесь , который обычно может тестировать более 3 000 000 кандидатных простых чисел в секунду на среднестатистическом портативном компьютере (и это с использованием неоптимизированного языка, такого как VB.net), и множить непростые числа для загрузки. В C ++ это могло быть легко в 5-20 раз быстрее.

Хотя существуют более эффективные алгоритмы, тест простоты Миллера-Рабина - один из самых простых для реализации.

Есть два разных вопроса:

1) Как найти , если число является простым числом? Если вы откроете для этого эффективный алгоритм, вы прославитесь в следующие 2000 лет;)

2) Как найти простые числа с точностью до предела N ?

вероятно, это то, о чем вы спрашиваете. Сито Аткина является наиболее эффективным, если ваш диапазон или предел N действительно большое число. В разумных пределах можно было бы реализовать оптимизированный вариант Сита Эратосфена. Я нашел эти два сайта более чем полезными:

• Сито Черного Ключа
• Сито Эратосфена

РЕДАКТИРОВАТЬ: @avakar

Хотя я более чем новичок в этом предмете, я не думаю AKS - ожидаемый алгоритм! удовлетворяют эквивалентности. Доказательство правильность для AKS состоит из показывая, что существует подходящий маленький r и подходящий небольшой набор целые числа A такие, что если для всех таких a в A тогда n должно быть простым.

Взгляните на существующие библиотеки, например OpenSSL и GNU MP.

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