Как проверить, является ли 10-значное число простым или нет?
Я знаю об алгоритме Сита и о том, что до сих пор использовал, чтобы получить простые числа на сумму до 1 миллиарда.
Но теперь мне нужно знать, является ли десятизначное число простым или нет, а алгоритм Сита не может вычислить это в срок.
Я много искал и наткнулся на простое тестирование Ферма, но оно не сработало, так как какую-то часть я не мог понять, а другая часть сказала, что оно только говорит, является ли это простое число или нет, с некоторой итерацией.
Я хочу знать, как я могу проверить, является ли такое большое число простым или меньше 1 секунды или около того? Какое решение / алгоритм было бы наиболее эффективным для этого?
Редактировать Я также добавляю свой код для алгоритма Sieve.
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();
}
}
Output for big numbers like this:
999999937
yes
took 24363 mills
Ответы 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;
}
}
Взял с здесь
Это O (sqrt (N)), Sieve намного лучше, но он все равно не дает результата в желаемое время.
Вы уверены, что эта временная сложность для написанного вами кода лучше, чем для таких больших чисел? Тот, который я нашел, работает менее 1 секунды для вашего номера.
Вы можете проверить, является ли это простым числом или нет:
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.");
}}
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
Я всегда использую этот код, чтобы проверить, является ли int простым
boolean isPrime(int x) {
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
return false;
}
}
return true;
}
Создавать решето только для проверки нескольких чисел неэффективно. Десятизначное число в этом контексте довольно мало, поскольку если оно не простое, оно должно иметь делитель между двумя и sqrt(9_999_999_999). Итак, вы проверяете, четное ли оно, а затем нужно проверить 50 тысяч кандидатов на делитель.
Если вы не хотите делать это самостоятельно, BigInteger.valueOf(x).isProbablePrime(certainty) есть прямо в JDK. Также в Гуава есть LongMath.isPrime(long x).
Вы проверяете числа до 9 999 999 999, поэтому вам нужен только список простых чисел до квадратного корня: 100 000. Любая композиция в этом диапазоне будет иметь как минимум один коэффициент ниже 100000. Если нет множителя ниже 100000, тогда число простое. Кроме того, вы используете массив логических значений для своего сита. При этом тратится много места, лучше использовать насадку для удержания сита, что экономит место.