How to create the most compact mapping n → isprime (n) to the limit of N?

Question

Naturally, for bool isprime(number) would be a data structure that I could query.
I define the best algorithm so that it is an algorithm that creates the data structure with the lowest memory consumption for the range (1, N], where N is a constant.
Just an example of what I'm looking for: I could represent every odd number with one bit, for example, for a given range of numbers (1, 10] starts at 3: 1110

The following dictionary can be compressed more, right? I could eliminate the multiple of five with some work, but numbers that end in 1, 3, 7 or 9 should be there in an array of bits.

How can I solve the problem?

Answer 1

There are many ways to perform a primary test .

There is actually no data structure for the query. If you have many numbers to test, you should probably run a probabilistic test because they are faster, and then run it with a deterministic test to make sure the number is prime.

You should know that the math behind the fastest algorithms is not for the faint of heart.

Answer 2

The fastest general simple testing algorithm is AKS . The Wikipedia article describes it in detail and links to the original paper.

If you want to find large numbers, look at primes that have special forms, such as Mersenne primes .

The algorithm that I usually implement (easy to understand and code) is as follows (in Python):

 def isprime(n): """Returns True if n is prime.""" if n == 2: return True if n == 3: return True if n % 2 == 0: return False if n % 3 == 0: return False i = 5 w = 2 while i * i <= n: if n % i == 0: return False i += w w = 6 - w return True 

This is a variant of the classic O(sqrt(N)) algorithm. He uses the fact that a simple (except for 2 and 3) has the form 6k - 1 or 6k + 1 and looks only on dividers of this form.

Sometimes, if I really need speed, and the range is limited, I implement a pseudo-test based on Fermat's theorem . If I really need extra speed (i.e., generally avoid the O (sqrt (N)) algorithm, I will pre-compromise the false positives (see Carmichael Numbers) and perform a binary search. This is by far the fastest test I have ever either implemented, the only drawback is that the range is limited.

Answer 3

The best method, in my opinion, is to use what was before.

There are lists of the first N primes on the Internet with N extending at least fifty million . Download files and use them, probably much faster than any other method you come up with.

If you need a real algorithm for creating your own primes, Wikipedia has all kinds of good things in simple words here , including links to various methods for this and initial testing here , both probability-based and quick determination methods.

A concerted effort must be made to find the first billions (or even more) of primes and publish them on the net somewhere, so that people can stop doing the same work again and again and again and ... :-)

Answer 4

 bool isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n%2 == 0 || n%3 == 0) return false; for (int i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return false; return true; } this is just c++ implementation of above AKS algorithm 

https://en.wikipedia.org/wiki/AKS_primality_test

Answer 5

According to wikipedia, Sieve of Eratosthenes is O(n * (log n) * (log log n)) complexity and requires O(n) memory - so this is a very good place to start if you are not testing especially large numbers.

Answer 6

In Python 3:

 def is_prime(a): if a < 2: return False elif a!=2 and a % 2 == 0: return False else: return all (a % i for i in range(3, int(a**0.5)+1)) 

Explanation: A prime number is a number that is divided only by itself and 1. Example: 2,3,5,7 ...

1) if a <2: if "a" is less than 2, this is not a prime.

2) elif a! = 2 and a% 2 == 0: if "a" is divisible by 2, then this is definitely not a prime number. But if a = 2, we do not want to evaluate this, since it is a prime. Hence the condition a! = 2

3) return everything (% i for i in the range (3, int (a 0.5) +1)): ** First, see what the all () command does in python. Starting from 3 we divide "a" to its square root (a ** 0.5). If "a" divides, the output will be false. Why square root? Let him say a = 16. The square root of 16 = 4. We do not need to evaluate to 15. We only need to check to 4 to say that this is not a prime number.

Optional: a loop to find all primes in a range.

 for i in range(1,100): if is_prime(i): print("{} is a prime number".format(i)) 

Answer 7

I compared the effectiveness of the most popular sentences to determine if a number is prime. I used python 3.6 on ubuntu 17.10 ; I checked with numbers up to 100,000 (you can check with large numbers using my code below).

This first graph compares the functions (which are explained later in my answer), showing that the last functions do not grow as fast as the first when the numbers increase.

And on the second graph we see that in the case of primes, time is steadily increasing, but not prime numbers are growing not so fast in time (since most of them can be eliminated at an early stage).

Here are the functions I used:

1. this answer and this answer suggested a construct using all() :

    def is_prime_1(n): return n > 1 and all(n % i for i in range(2, int(math.sqrt(n)) + 1)) 

2. This answer used some kind of while loop:

    def is_prime_2(n): if n <= 1: return False if n == 2: return True if n == 3: return True if n % 2 == 0: return False if n % 3 == 0: return False i = 5 w = 2 while i * i <= n: if n % i == 0: return False i += w w = 6 - w return True 

3. This answer included a version with a for loop:

    def is_prime_3(n): if n <= 1: return False if n % 2 == 0 and n > 2: return False for i in range(3, int(math.sqrt(n)) + 1, 2): if n % i == 0: return False return True 

4. And I mixed several ideas from the other answers into a new one:

    def is_prime_4(n): if n <= 1: # negative numbers, 0 or 1 return False if n <= 3: # 2 and 3 return True if n % 2 == 0 or n % 3 == 0: return False for i in range(5, int(math.sqrt(n)) + 1, 2): if n % i == 0: return False return True 

---

Here is my script for comparing options:

 import math import pandas as pd import seaborn as sns import time from matplotlib import pyplot as plt def is_prime_1(n): ... def is_prime_2(n): ... def is_prime_3(n): ... def is_prime_4(n): ... default_func_list = (is_prime_1, is_prime_2, is_prime_3, is_prime_4) def assert_equal_results(func_list=default_func_list, n): for i in range(-2, n): r_list = [f(i) for f in func_list] if not all(r == r_list[0] for r in r_list): print(i, r_list) raise ValueError print('all functions return the same results for integers up to {}'.format(n)) def compare_functions(func_list=default_func_list, n): result_list = [] n_measurements = 3 for f in func_list: for i in range(1, n + 1): ret_list = [] t_sum = 0 for _ in range(n_measurements): t_start = time.perf_counter() is_prime = f(i) t_end = time.perf_counter() ret_list.append(is_prime) t_sum += (t_end - t_start) is_prime = ret_list[0] assert all(ret == is_prime for ret in ret_list) result_list.append((f.__name__, i, is_prime, t_sum / n_measurements)) df = pd.DataFrame( data=result_list, columns=['f', 'number', 'is_prime', 't_seconds']) df['t_micro_seconds'] = df['t_seconds'].map(lambda x: round(x * 10**6, 2)) print('df.shape:', df.shape) print() print('', '-' * 41) print('| {:11s} | {:11s} | {:11s} |'.format( 'is_prime', 'count', 'percent')) df_sub1 = df[df['f'] == 'is_prime_1'] print('| {:11s} | {:11,d} | {:9.1f} % |'.format( 'all', df_sub1.shape[0], 100)) for (is_prime, count) in df_sub1['is_prime'].value_counts().iteritems(): print('| {:11s} | {:11,d} | {:9.1f} % |'.format( str(is_prime), count, count * 100 / df_sub1.shape[0])) print('', '-' * 41) print() print('', '-' * 69) print('| {:11s} | {:11s} | {:11s} | {:11s} | {:11s} |'.format( 'f', 'is_prime', 't min (us)', 't mean (us)', 't max (us)')) for f, df_sub1 in df.groupby(['f', ]): col = df_sub1['t_micro_seconds'] print('|{0}|{0}|{0}|{0}|{0}|'.format('-' * 13)) print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format( f, 'all', col.min(), col.mean(), col.max())) for is_prime, df_sub2 in df_sub1.groupby(['is_prime', ]): col = df_sub2['t_micro_seconds'] print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format( f, str(is_prime), col.min(), col.mean(), col.max())) print('', '-' * 69) return df 

Running the compare_functions(n=10**5) function compare_functions(n=10**5) (numbers up to 100,000) I get this output:

 df.shape: (400000, 5) ----------------------------------------- | is_prime | count | percent | | all | 100,000 | 100.0 % | | False | 90,408 | 90.4 % | | True | 9,592 | 9.6 % | ----------------------------------------- --------------------------------------------------------------------- | f | is_prime | t min (us) | t mean (us) | t max (us) | |-------------|-------------|-------------|-------------|-------------| | is_prime_1 | all | 0.57 | 2.50 | 154.35 | | is_prime_1 | False | 0.57 | 1.52 | 154.35 | | is_prime_1 | True | 0.89 | 11.66 | 55.54 | |-------------|-------------|-------------|-------------|-------------| | is_prime_2 | all | 0.24 | 1.14 | 304.82 | | is_prime_2 | False | 0.24 | 0.56 | 304.82 | | is_prime_2 | True | 0.25 | 6.67 | 48.49 | |-------------|-------------|-------------|-------------|-------------| | is_prime_3 | all | 0.20 | 0.95 | 50.99 | | is_prime_3 | False | 0.20 | 0.60 | 40.62 | | is_prime_3 | True | 0.58 | 4.22 | 50.99 | |-------------|-------------|-------------|-------------|-------------| | is_prime_4 | all | 0.20 | 0.89 | 20.09 | | is_prime_4 | False | 0.21 | 0.53 | 14.63 | | is_prime_4 | True | 0.20 | 4.27 | 20.09 | --------------------------------------------------------------------- 

Then, by running the compare_functions(n=10**6) function compare_functions(n=10**6) (numbers up to 1.000.000), I get the following output:

 df.shape: (4000000, 5) ----------------------------------------- | is_prime | count | percent | | all | 1,000,000 | 100.0 % | | False | 921,502 | 92.2 % | | True | 78,498 | 7.8 % | ----------------------------------------- --------------------------------------------------------------------- | f | is_prime | t min (us) | t mean (us) | t max (us) | |-------------|-------------|-------------|-------------|-------------| | is_prime_1 | all | 0.51 | 5.39 | 1414.87 | | is_prime_1 | False | 0.51 | 2.19 | 413.42 | | is_prime_1 | True | 0.87 | 42.98 | 1414.87 | |-------------|-------------|-------------|-------------|-------------| | is_prime_2 | all | 0.24 | 2.65 | 612.69 | | is_prime_2 | False | 0.24 | 0.89 | 322.81 | | is_prime_2 | True | 0.24 | 23.27 | 612.69 | |-------------|-------------|-------------|-------------|-------------| | is_prime_3 | all | 0.20 | 1.93 | 67.40 | | is_prime_3 | False | 0.20 | 0.82 | 61.39 | | is_prime_3 | True | 0.59 | 14.97 | 67.40 | |-------------|-------------|-------------|-------------|-------------| | is_prime_4 | all | 0.18 | 1.88 | 332.13 | | is_prime_4 | False | 0.20 | 0.74 | 311.94 | | is_prime_4 | True | 0.18 | 15.23 | 332.13 | --------------------------------------------------------------------- 

---

To build the results, I used the following script:

 def plot_1(func_list=default_func_list, n): df_orig = compare_functions(func_list=func_list, n=n) df_filtered = df_orig[df_orig['t_micro_seconds'] <= 20] sns.lmplot( data=df_filtered, x='number', y='t_micro_seconds', col='f', # row='is_prime', markers='.', ci=None) plt.ticklabel_format(style='sci', axis='x', scilimits=(3, 3)) plt.show() 

Answer 8

You can use sympy .

 import sympy sympy.ntheory.primetest.isprime(33393939393929292929292911111111) True 

From simplex documents. The first step is to search for trivial factors that, if found, allow you to quickly return. Then, if the sieve is large enough, use the bisection search on the sieve. For small numbers, the set of deterministic Miller-Rabin tests is performed with bases that, as you know, have no counterexamples in their range. Finally, if the number is greater than 2 ^ 64, a strong BPSW test is performed. Although this is a likely primary test, and we believe that counterexamples exist, there are no known counterexamples

Answer 9

For large numbers, you cannot simply naively check if the number of candidates N is divisible by one of the numbers less than sqrt (N). Much more scalable tests are available, such as the Miller-Rabin primary test . Below you have an implementation in Python:

 def is_prime(x): """Fast implementation fo Miller-Rabin primality test, guaranteed to be correct.""" import math def get_sd(x): """Returns (s: int, d: int) for which x = d*2^s """ if not x: return 0, 0 s = 0 while 1: if x % 2 == 0: x /= 2 s += 1 else: return s, x if x <= 2: return x == 2 # x - 1 = d*2^s s, d = get_sd(x - 1) if not s: return False # divisible by 2! log2x = int(math.log(x) / math.log(2)) + 1 # As long as Riemann hypothesis holds true, it is impossible # that all the numbers below this threshold are strong liars. # Hence the number is guaranteed to be a prime if no contradiction is found. threshold = min(x, 2*log2x*log2x+1) for a in range(2, threshold): # From Fermat little theorem if x is a prime then a^(x-1) % x == 1 # Hence the below must hold true if x is indeed a prime: if pow(a, d, x) != 1: for r in range(0, s): if -pow(a, d*2**r, x) % x == 1: break else: # Contradicts Fermat little theorem, hence not a prime. return False # No contradiction found, hence x must be a prime. return True 

You can use it to find huge prime numbers:

 x = 10000000000000000000000000000000000000000000000000000000000000000000000000000 for e in range(1000): if is_prime(x + e): print('%d is a prime!' % (x + e)) break # 10000000000000000000000000000000000000000000000000000000000000000000000000133 is a prime! 

If you are testing random integers, you might want to first check to see if the number of candidates is divisible by any of the primes smaller than, for example, 1000 before calling Miller-Rabin. This will help you filter out obvious non prime numbers such as 10444344345.

Answer 10

Python 3:

 def is_prime(a): return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1)) 

Answer 11

Too late for the party, but hope this helps. This is true if you are looking for large prime numbers:

To check for large odd numbers, you need to use the Fermat-test and / or Miller-Rabin.

These tests use modular exponentiation, which is quite expensive, for exponenting n bits you need at least n large int multiplications and n large int divison multiplications. This means that the complexity of modular exponentiation is O (n³).

Therefore, before using large guns, you need to do a few test divisions. But do not do it naively, there is a way to make them quickly. First, multiply as many primes together as fit into the words you use for large integers. If you use 32-bit words, multiply 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 3234846615 and calculate the largest common factor with the number that you will check using the Euclidean algorithm. After the first step, the number decreases below the word size and continues the algorithm without performing complete large integer divisions. If GCD! = 1, this means that one of the prime numbers you multiplied divides the number, so you have proof that it is not prime. Then continue with 31 * 37 * 41 * 43 * 47 = 95041567 and so on.

After you have checked several hundred (or thousands) primes in this way, you can perform 40 rounds of the Miller-Rabin test to confirm that the number is prime, after 40 rounds you can be sure that the number is prime, there is only a 2 ^ -80 probability is not (rather, your hardware malfunctions ...).

Answer 12

I have a main function that works up to (2 ^ 61) -1 Here:

 from math import sqrt def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1))) 

Explanation:

The all() function can be overridden as follows:

 def all(variables): for element in variables: if not element: return False return True 

The all() function simply goes through a series of bools / numbers and returns False if it sees 0 or False .

The sqrt() function simply does the square root of a number.

For example:

 >>> from math import sqrt >>> sqrt(9) >>> 3 >>> sqrt(100) >>> 10 

The num % x part returns the remaining num / x part.

Finally, range(2, int(sqrt(num))) means that it will create a list starting with 2 and ending with int(sqrt(num)+1)

For more information about the range, look at this site !

The num > 1 parameter simply checks to see if the num variable is greater than 1, because 1 and 0 are not considered prime numbers.

Hope this helps :)

Answer 13

In Python:

 def is_prime(n): return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1)) 

A more direct conversion from mathematical formalism to Python will use everything (n% p! = 0 ...) , but this requires a rigorous evaluation of all p values. Not every version can end earlier if a True value is found.

Answer 14

best algorithm for Primes javascript number

  function isPrime(num) { if (num <= 1) return false; else if (num <= 3) return true; else if (num % 2 == 0 || num % 3 == 0) return false; var i = 5; while (i * i <= num) { if (num % i == 0 || num % (i + 2) == 0) return false; i += 6; } return true } 

Answer 15

 import math import time def check_prime(n): if n == 1: return False if n == 2: return True if n % 2 == 0: return False from_i = 3 to_i = math.sqrt(n) + 1 for i in range(from_i, int(to_i), 2): if n % i == 0: return False return True 

Answer 16

A similar idea with the AKS algorithm mentioned

 public static boolean isPrime(int n) { if(n == 2 || n == 3) return true; if((n & 1 ) == 0 || n % 3 == 0) return false; int limit = (int)Math.sqrt(n) + 1; for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) { if(n % i == 0) return false; numChecks++; } return true; } 

Answer 17

To find out if a number or numbers in a range / base.

 #!usr/bin/python3 def prime_check(*args): for arg in args: if arg > 1: # prime numbers are greater than 1 for i in range(2,arg): # check for factors if(arg % i) == 0: print(arg,"is not Prime") print(i,"times",arg//i,"is",arg) break else: print(arg,"is Prime") # if input number is less than # or equal to 1, it is not prime else: print(arg,"is not Prime") return # Calling Now prime_check(*list(range(101))) # This will check all the numbers in range 0 to 100 prime_check(#anynumber) # Put any number while calling it will check. 

Answer 18

 myInp=int(input("Enter a number: ")) if myInp==1: print("The number {} is neither a prime not composite no".format(myInp)) elif myInp>1: for i in range(2,myInp//2+1): if myInp%i==0: print("The Number {} is not a prime no".format(myInp)) print("Because",i,"times",myInp//i,"is",myInp) break else: print("The Number {} is a prime no".format(myInp)) else: print("Alas the no {} is a not a prime no".format(myInp)) 

Answer 19

You could try something like this.

 def main(): try: user_in = int(input("Enter a number to determine whether the number is prime or not: ")) except ValueError: print() print("You must enter a number!") print() return list_range = list(range(2,user_in+1)) divisor_list = [] for number in list_range: if user_in%number==0: divisor_list.append(number) if len(divisor_list) < 2: print(user_in, "is a prime number!") return else: print(user_in, "is not a prime number!") return main() 

Answer 20

Most of the previous answers are correct, but here is another way to check if a number is a prime number. As a second update, prime numbers are integers greater than 1, the only factors of which are 1 and itself ( source )

Decision:

Typically, you can build a loop and start testing your number to see if it divides by 1,2,3 ... to the number you are testing ... etc., but to shorten the verification time, you You can divide your number by half the value of your number, because a number cannot be exactly divided by anything above half its value. For example, if you want to see 100, this is a prime number that you can scroll to 50.

Actual code :

 def find_prime(number): if(number ==1): return False # we are dividiing and rounding and then adding the remainder to increment ! # to cover not fully divisible value to go up forexample 23 becomes 11 stop=number//2+number%2 #loop through up to the half of the values for item in range(2,stop): if number%item==0: return False print(number) return True if(find_prime(3)): print("it a prime number !!") else: print("it not a prime") 

Answer 21

We can use java threads to implement this in O (sqrt (n)); Note that noneMatch is a shortCircuiting method that stops the operation if there is no need to determine the result:

 Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.println(n == 2 ? "Prime" : IntStream.rangeClosed(2, ((int)(Math.sqrt(n)) + 1)).noneMatch(a -> n % a == 0) ? "Prime" : "Not Prime"); 

Answer 22

Using Java-8 threads and lambdas, this can be implemented as follows:

 public static boolean isPrime(int candidate){ int candidateRoot = (int) Math.sqrt( (double) candidate); return IntStream.range(2,candidateRoot) .boxed().noneMatch(x -> candidate % x == 0); } 

Performance should be close to O (sqrt (N)). Maybe someone will find this helpful.

Answer 23

Here is my view on the answer:

 def isprime(num): return num <= 3 or (num + 1) % 6 == 0 or (num - 1) % 6 == 0 

The function will return True if any of the following properties is True. These properties mathematically determine what a prime number is.

1. Number less than or equal to 3
2. The number + 1 is divided by 6
3. The number - 1 is divided by 6

Answer 24

A prime number is any number that is divisible by only 1 and by itself. All other numbers are called compound.

The easiest way to find a prime number is to check if the entered number is a composite number:

  function isPrime(number) { // Check if a number is composite for (let i = 2; i < number; i++) { if (number % i === 0) { return false; } } // Return true for prime numbers return true; } 

The program should divide the value of number by all integers from 1 to its value. If this number can be divided equally not only into one, but in fact, this is a composite number.

The initial value of the variable i must be 2, because both prime and composite numbers can be evenly divided by 1.

  for (let i = 2; i < number; i++) 

Then i less than number for the same reason. Prime and compound numbers can be evenly divided among themselves. Therefore, there is no reason to verify this.

Then we check if the variable can be divided evenly using the remainder operator.

  if (number % i === 0) { return false; } 

If the remainder is zero, this means that number can be divided evenly, hence the composite number and return false.

If the entered number does not satisfy the condition, this means that it is a prime number, and the function returns true.

Answer 25

? , .

 class PrimeDictionary { BitArray bits; public PrimeDictionary(int n) { bits = new BitArray(n + 1); for (int i = 0; 2 * i + 3 <= n; i++) { bits.Set(i, CheckPrimality(2 * i + 3)); } } public PrimeDictionary(IEnumerable<int> primes) { bits = new BitArray(primes.Max()); foreach(var prime in primes.Where(p => p != 2)) { bits.Set((prime - 3) / 2, true); } } public bool IsPrime(int k) { if (k == 2) { return true; } if (k % 2 == 0) { return false; } return bits[(k - 3) / 2]; } } 

, CheckPrimality .

Answer 26

, , .

 void prime(long long int number) { // Establishing Variables long long int i = 5; int w = 2; const long long int lim = sqrt(number); // Gets 2 and 3 out of the way if (number == 1) { cout << number << " is hard to classify. \n"; return; } if (number == 2) { cout << number << " is Prime. \n"; return; } if (number == 3) { cout << number << " is Prime. \n"; return; } // Tests Odd Ball Factors if (number % 2 == 0) { cout << number << " is not Prime. \n"; return; } if (number % 3 == 0) { cout << number << " is not Prime. \n"; return; } while (i <= lim) { if (number % i == 0) { cout << number << " is not Prime. \n"; return; } // Tests Number i = i + w; // Increments number w = 6 - i; // We already tested 2 and 3 // So this removes testing multepules of this } cout << number << " is Prime. \n"; return; } 

Answer 27

You can try this code:

 def isprime(n): if n == 1: return False for i in range(2,int(n**0.5)+1): if n%i==0: return False return True 

, isprime(NUMBER)

, , :

 def isprime(n): if n == 1: return False for i in range(2,int(n**0.5)+1): if n%i==0: return False return True while True: number = input('Please Enter A Number: ') if isprime(int(number)): print('The Number You Entered Is A Prime Number', end='\n\n') else: print('The Number You Entered Is Not A Prime Number', end='\n\n') 

Answer 28

 public class PrimeNumberOrNot { public static void main(String[] args) { System.out.println(isPrimeOrNot(12345673)); } public static String isPrimeOrNot(int num) { if (num < 0) { return "not valid"; } if (num == 0 || num == 1) { return "not prime"; } if (num == 2 || num == 3) { return "prime number"; } if ((num * num - 1) % 24 == 0) { return "prime"; } else { return "not prime"; } } } 

Answer 29

 public static boolean isPrime(int number) { if(number < 2) return false; else if(number == 2 || number == 3) return true; else { for(int i=2;i<=number/2;i++) if(number%i == 0) return false; else if(i==number/2) return true; } return false; } 

Answer 30

The first rule of a prime number: if you divide by 2, it will be an integer or an integer No, this is not a prime number.

The fastest way to learn using any computer language is type matching using strings, not math. Match the DOT in the string float.

• Divide this by 2 ,, n = n / 2
• Convert this to a string ,, n = string (n)
• if "." in p: {printf "Yes, I'm prime!"