Как проверить, простое ли 10-значное число или нет?

Question

Я знаю об алгоритме Сита и который я использовал до сих пор, чтобы получить простые числа до 1 млрд.

Но теперь мне нужно знать, простое ли 10-значное число, и алгоритм Сита можетне вычисляю это в срок.

Я много искал и наткнулся на первичное тестирование Ферма, но это не сработало, так как какая-то часть я не могла понять, а другая говорила, что это говорит только о том,возможно, это простое число или нет с некоторой итерацией.

Я хочу знать, как я могу проверить, является ли большое число простым или нет, менее чем за 1 секунду или около того?Что было бы наиболее эффективным решением / алгоритмом для этого?

Редактировать Я также добавляю свой код для алгоритма Сита.

public class Random18 {

    public static int sieveOfEratosthenes(int n) 
    { 
        // Create a boolean array "prime[0..n]" and initialize 
        // all entries it as true. A value in prime[i] will 
        // finally be false if i is Not a prime, else true. 
        boolean primes[] = new boolean[n+1]; 
        Arrays.fill(primes,true);        // assume all integers are prime.

        primes[0]=primes[1]=false;       // we know 0 and 1 are not prime.
        for (int i=2;i<primes.length;i++) {
            //if the number is prime, 
            //then go through all its multiples and make their values false.
            if(primes[i]) {
                for (int j=2;i*j<primes.length;j++) {
                    primes[i*j]=false;
                }
            }
        }
        if(primes[n]==true)
            return 1;

        else
            return 0;
    } 


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter");

        int p = scanner.nextInt();

        long t1 = System.currentTimeMillis();

        int k = sieveOfEratosthenes(p);

        long t2 = System.currentTimeMillis();

        if(k==1)
            System.out.println("yes");

        else
            System.out.println("no");

        System.out.println("took "+(t2-t1)+" millis");


        scanner.close();
    }

}

Вывод для большихчисла, подобные этому:
999999937
да
заняло 24363 мельницы

Answer 1

Неэффективно создавать сито только для проверки нескольких чисел.Десятизначное число в этом контексте довольно мало, так как если оно не простое, оно должно иметь делитель между двумя и sqrt(9_999_999_999).Таким образом, вы проверяете, является ли оно четным, и тогда нужно проверить кандидатов на деление 50 000

1003 * Если вы не хотите делать это самостоятельно, прямо в JDK есть BigInteger.valueOf(x).isProbablePrime(certainty).Также есть LongMath.isPrime(long x) в гуаве .

Answer 2

Я всегда использую этот код, чтобы проверить, является ли int простым

boolean isPrime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

Answer 3

Вы можете проверить, является ли это простым числом или нет:

public class Prime {

public static void main(String[] args) {

    int num = 10;
    boolean flag = false;
    for(int i = 2, max = num/2; i <= max; ++i)
    {
        // condition for nonprime number
        if(num % i == 0)
        {
            flag = true;
            break;
        }
    }

    if (!flag)
        System.out.println(num + " is a prime number.");
    else
        System.out.println(num + " is not a prime number.");
}}

Answer 4

public static void main(String[] args) {
    try (Scanner scan = new Scanner(System.in)) {
        System.out.print("Enter: ");
        long val = scan.nextLong();
        long t1 = System.currentTimeMillis();
        System.out.println(isPrime.test(val) ? "yes" : "no");
        System.out.println("took " + (System.currentTimeMillis() - t1) + " millis");
    }
}

static final LongPredicate isPrime = val -> {
    if (val < 2)
        return false;

    for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
        if (val % i == 0)
            return false;

    return true;
};

Выход:

Enter: 999999937
yes
took 1 millis

Answer 5

Этот метод пропускает все четные числа и пробует только до квадратного корня числа.Он работает нормально для вашего заданного номера

public class Prime {
    public static void main(String[] args) {
        isPrime(999999937L);
    }

    public static boolean isPrime(long num) {
        if (num > 2 && num % 2 == 0) {
            System.out.println(num + " is not prime");
            return false;
        }
        int top = (int) Math.sqrt(num) + 1;
        for (int i = 3; i < top; i += 2) {
            if (num % i == 0) {
                System.out.println(num + " is not prime");
                return false;
            }
        }
        System.out.println(num + " is prime");
        return true;
    }
}

Я взял его от здесь