Обработка больших входов для моего теста java primality? [Дубликат]
Вы можете использовать эту пользовательскую библиотеку (написанную с помощью Promise) для выполнения удаленного вызова.
function $http(apiConfig) {
return new Promise(function (resolve, reject) {
var client = new XMLHttpRequest();
client.open(apiConfig.method, apiConfig.url);
client.send();
client.onload = function () {
if (this.status >= 200 && this.status < 300) {
// Performs the function "resolve" when this.status is equal to 2xx.
// Your logic here.
resolve(this.response);
}
else {
// Performs the function "reject" when this.status is different than 2xx.
reject(this.statusText);
}
};
client.onerror = function () {
reject(this.statusText);
};
});
}
Пример простого использования:
$http({
method: 'get',
url: 'google.com'
}).then(function(response) {
console.log(response);
}, function(error) {
console.log(error)
});
13 ответов
Вот еще один способ:
boolean isPrime(long n) {
if(n < 2) return false;
if(n == 2 || n == 3) return true;
if(n%2 == 0 || n%3 == 0) return false;
long sqrtN = (long)Math.sqrt(n)+1;
for(long i = 6L; i <= sqrtN; i += 6) {
if(n%(i-1) == 0 || n%(i+1) == 0) return false;
}
return true;
}
и BigInteger's isProbablePrime(...) допустим для всех 32-битных int.
EDIT
Обратите внимание, что isProbablePrime(certainty) не всегда дает правильный ответ. Когда определенность находится на нижней стороне, она создает ложные срабатывания, как указано в комментариях @ dimo414.
К сожалению, я не смог найти источник, который утверждал, что isProbablePrime(certainty) действителен для всех (32-разрядный ) int (с достаточной уверенностью!).
Итак, я выполнил пару тестов. Я создал BitSet размера Integer.MAX_VALUE/2, представляющего все неравные числа, и использовал первичное сито, чтобы найти все простые числа в диапазоне 1..Integer.MAX_VALUE. Затем я зациклился от i=1..Integer.MAX_VALUE, чтобы проверить, что каждый new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i).
Для достоверности 5 и 10, isProbablePrime(...) произвели ложные срабатывания вдоль линии. Но с isProbablePrime(15) тест не сработал.
Вот моя тестовая установка:
import java.math.BigInteger;
import java.util.BitSet;
public class Main {
static BitSet primes;
static boolean isPrime(int p) {
return p > 0 && (p == 2 || (p%2 != 0 && primes.get(p/2)));
}
static void generatePrimesUpTo(int n) {
primes = new BitSet(n/2);
for(int i = 0; i < primes.size(); i++) {
primes.set(i, true);
}
primes.set(0, false);
int stop = (int)Math.sqrt(n) + 1;
int percentageDone = 0, previousPercentageDone = 0;
System.out.println("generating primes...");
long start = System.currentTimeMillis();
for(int i = 0; i <= stop; i++) {
previousPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (stop / 100.0));
if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
System.out.println(percentageDone + "%");
}
if(primes.get(i)) {
int number = (i * 2) + 1;
for(int p = number * 2; p < n; p += number) {
if(p < 0) break; // overflow
if(p%2 == 0) continue;
primes.set(p/2, false);
}
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished generating primes ~" + (elapsed/1000) + " seconds");
}
private static void test(final int certainty, final int n) {
int percentageDone = 0, previousPercentageDone = 0;
long start = System.currentTimeMillis();
System.out.println("testing isProbablePrime(" + certainty + ") from 1 to " + n);
for(int i = 1; i < n; i++) {
previousPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (n / 100.0));
if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
System.out.println(percentageDone + "%");
}
BigInteger bigInt = new BigInteger(String.valueOf(i));
boolean bigIntSays = bigInt.isProbablePrime(certainty);
if(isPrime(i) != bigIntSays) {
System.out.println("ERROR: isProbablePrime(" + certainty + ") returns "
+ bigIntSays + " for i=" + i + " while it " + (isPrime(i) ? "is" : "isn't" ) +
" a prime");
return;
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished testing in ~" + ((elapsed/1000)/60) +
" minutes, no false positive or false negative found for isProbablePrime(" + certainty + ")");
}
public static void main(String[] args) {
int certainty = Integer.parseInt(args[0]);
int n = Integer.MAX_VALUE;
generatePrimesUpTo(n);
test(certainty, n);
}
}
, которую я выполнил:
java -Xmx1024m -cp . Main 15
из простых чисел на моей машине было ~ 30 секунд. И фактическое испытание всех i в 1..Integer.MAX_VALUE заняло около 2 часов и 15 минут.
-
1– Anantha Kumaran 5 March 2010 в 11:39
-
2– Bart Kiers 5 March 2010 в 11:58
-
3– Anantha Kumaran 5 March 2010 в 12:01
-
4– dimo414 29 October 2010 в 10:04
-
5– tb- 30 March 2013 в 14:01
Ваш алгоритм будет хорошо работать для достаточно малых чисел. Для больших чисел следует использовать передовые алгоритмы (например, на эллиптических кривых). Другая идея будет заключаться в использовании некоторых тестов «псевдопробы». Они будут быстро проверять, что число является простым, но они не на 100% точны. Тем не менее, они могут помочь вам исключить некоторые цифры быстрее, чем с вашим алгоритмом.
Наконец, хотя компилятор, вероятно, оптимизирует это для вас, вы должны написать:
int max = (int) (Math.sqrt(n) + 1);
for (int i = 3; i <= max; i = i + 2) {
}
Я думаю, что этот метод лучше. по крайней мере для меня -
public static boolean isPrime(int num)
{
for (int i = 2; i<= num/i; i++)
{
if (num % i == 0)
{
return false;
}
}
return num > 1;
}
Есть, конечно, сотни тестов примитивности, все из которых имеют различные преимущества и недостатки, основанные на размере числа, специальных формах, размере фактора и т. д.
Однако в java я нахожу наиболее полезным это:
BigInteger.valueOf(long/int num).isProbablePrime(int certainty);
Его уже реализовано и довольно быстро (я нахожу, что для матрицы 1000x1000, заполненной длинными 0-2 ^ 64 и уверенностью 15, требуется ~ 6 секунд) и, вероятно, лучше оптимизирован, чем все, что могли бы предложить смертные.
Он использует версию теста Baillie-PSW primality , которая не знает контрпримеры. (хотя он может использовать немного более слабую версию теста, что иногда может ошибиться).
В зависимости от длины числа, которое необходимо проверить, вы можете предварительно скопировать список простых чисел для небольших значений (n & lt; 10 ^ 6), который используется первым, если запрашиваемый номер находится в этом диапазоне. Это, конечно, самый быстрый путь. Как упоминалось в других ответах, сито Эратосфена является предпочтительным способом генерации такого предварительно вычисленного списка.
Если ваши цифры больше этого, вы можете использовать тест прочности Рабина , Тест на первичность Рабина
Быстрый тест из-за Jaeschke (1993) является детерминированной версией теста Миллера-Рабина, который не имеет ложных срабатываний ниже 4,759,123,141 и поэтому может быть применен к Java int s.
// Given a positive number n, find the largest number m such
// that 2^m divides n.
private static int val2(int n) {
int m = 0;
if ((n&0xffff) == 0) {
n >>= 16;
m += 16;
}
if ((n&0xff) == 0) {
n >>= 8;
m += 8;
}
if ((n&0xf) == 0) {
n >>= 4;
m += 4;
}
if ((n&0x3) == 0) {
n >>= 2;
m += 2;
}
if (n > 1) {
m++
}
return m;
}
// For convenience, handle modular exponentiation via BigInteger.
private static int modPow(int base, int exponent, int m) {
BigInteger bigB = BigInteger.valueOf(base);
BigInteger bigE = BigInteger.valueOf(exponent);
BigInteger bigM = BigInteger.valueOf(m);
BigInteger bigR = bigB.modPow(bigE, bigM);
return bigR.intValue();
}
// Basic implementation.
private static boolean isStrongProbablePrime(int n, int base) {
int s = val2(n-1);
int d = modPow(b, n>>s, n);
if (d == 1) {
return true;
}
for (int i=1; i < s; i++) {
if (d+1 == n) {
return true;
}
d = d*d % n;
}
return d+1 == n;
}
public static boolean isPrime(int n) {
if ((n&1) == 0) {
return n == 2;
}
if (n < 9) {
return n > 1;
}
return isStrongProbablePrime(n, 2) && isStrongProbablePrime(n, 7) && isStrongProbablePrime(n, 61);
}
Это не работает для переменных long, но другой тест: тест BPSW не имеет контрпримеров до 2 ^ 64. Это в основном состоит из 2-сильного вероятного простого теста, такого как выше, за которым следует сильный тест Lucas, который немного сложнее, но не принципиально отличается.
Оба этих теста намного быстрее, чем любое пробное деление .
Я оптимизировал пробное подразделение здесь: он возвращает логическое значение. Также необходимы методы, отличные от isPrime (n).
static boolean[] smlprime = {false, false, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false};
public static boolean isPrime(long n) { //optimised
if (n < 2) {
return false;
}
if (n < smlprime.length) //less than smlprime.length do not need to be checked
{
return smlprime[(int) n]; //lol already checked
}
long[] dgt = longDigits(n);
long ones = dgt[dgt.length - 1];
if (ones % 2 == 0) {
return false;
}
if (ones == 0 || ones == 5) {
return false;
}
if (digitadd(n) % 3 == 0) {
return false;
}
if (n % 7 == 0) {
return false;
}
if (Square(n)) {
return false;
}
long hf = (long) Math.sqrt(n);
for (long j = 11; j < hf; j = nextProbablePrime(j)) {
//System.out.prlongln(Math.sqrt(i));
if (n % j == 0) {
return false;
}
//System.out.prlongln("res"+res);
}
return true;
}
public static long nextProbablePrime(long n) {
for (long i = n;; i++) {
if (i % 2 != 0 && i % 3 != 0 && i % 7 != 0) {
return i;
}
}
}
public static boolean Square(long n) {
long root = (long) Math.sqrt(n);
return root * root == n;
}
public static long[] longDigits(long n) {
String[] a = Long.toString(n).split("(?!^)");
long[] out = new long[a.length];
for (int i = 0; i < a.length; i++) {
out[i] = Long.parseLong(a[i]);
}
return out;
}
public static long digitadd(long n) {
long[] dgts = longDigits(n);
long ans = 0;
for (long i : dgts) {
ans += i;
}
return ans;
}
То, что вы написали, - это то, что делают большинство обычных программистов и которое должно быть достаточным в большинстве случаев.
Однако, если вы после «наилучшего научного алгоритма», существует множество вариантов (с различными уровнями (g0) http://en.wikipedia.org/wiki/Prime_number .
Например, если у вас есть 70-значный номер, физические ограничения JVM могут помешать вашему коду в этом случае вы можете использовать «Сита» и т. д.
Опять же, как я уже сказал, если это был вопрос программирования или общий вопрос использования в программном обеспечении, ваш код должен быть идеальным:)
Эффективность алгоритма: O (n ^ (1/2)) Алгоритм
Примечание. В этом примере кода ниже приведены счетные переменные и вызовы функции печати для печати результатов:
import java.util.*;
class Primality{
private static void printStats(int count, int n, boolean isPrime) {
System.err.println( "Performed " + count + " checks, determined " + n
+ ( (isPrime) ? " is PRIME." : " is NOT PRIME." ) );
}
/**
* Improved O( n^(1/2)) ) Algorithm
* Checks if n is divisible by 2 or any odd number from 3 to sqrt(n).
* The only way to improve on this is to check if n is divisible by
* all KNOWN PRIMES from 2 to sqrt(n).
*
* @param n An integer to be checked for primality.
* @return true if n is prime, false if n is not prime.
**/
public static boolean primeBest(int n){
int count = 0;
// check lower boundaries on primality
if( n == 2 ){
printStats(++count, n, true);
return true;
} // 1 is not prime, even numbers > 2 are not prime
else if( n == 1 || (n & 1) == 0){
printStats(++count, n, false);
return false;
}
double sqrtN = Math.sqrt(n);
// Check for primality using odd numbers from 3 to sqrt(n)
for(int i = 3; i <= sqrtN; i += 2){
count++;
// n is not prime if it is evenly divisible by some 'i' in this range
if( n % i == 0 ){
printStats(++count, n, false);
return false;
}
}
// n is prime
printStats(++count, n, true);
return true;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
int n = scan.nextInt();
primeBest(n);
System.out.println();
}
scan.close();
}
}
Когда введено простое число 2147483647, он производит следующий вывод:
Выполнено 23170 проверок, определено 2147483647 является PRIME.
Если вы просто пытаетесь найти, является ли число простым или нет, это достаточно хорошо, но если вы пытаетесь найти все простые числа от 0 до na, лучшим вариантом будет сито Eratosthenes
Но это будет зависеть от ограничений java на размерах массива и т. д.
Это самый элегантный способ:
public static boolean isPrime(int n) {
return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
Java 1.4+. Импорт не требуется.
Так коротка. Так красиво.
-
1– bgroenks 7 June 2012 в 05:43
-
2– user102008 7 June 2012 в 09:20
-
3– Paul Cantrell 19 February 2013 в 02:05
-
4– Esailija 14 May 2013 в 10:25
-
5– wvdz 23 April 2014 в 19:15
Взгляните на тест присадки AKS (и его различные оптимизации). Это детерминированный тест примитивности, который выполняется в полиномиальное время.
Здесь имеется реализация алгоритма в Java из Университета Тюбингена (Германия)
-
1– Honza Zidek 1 June 2015 в 08:45
-
2– DanaJ 25 April 2017 в 00:10
-
3– l'L'l 12 March 2018 в 09:20