How to create the most compact mapping n isprime n up to a limit N

Question

Naturally  for bool isprime number  there would be a data structure I could query  I define the best algorithm  to be the algorithm that produces a data structure with lowest memory consumption for the range  1  N   where N is a constant  Just an example of what I am looking for  I could represent every odd number with one bit e g  for the given range of numbers  1  10   starts at 3  1110    The following dictionary can be squeezed more  right  I could eliminate multiples of five with some work  but numbers that end with 1  3  7 or 9 must be there in the array of bits    How do I solve the problem

User · Answer

bool isPrime int n    if n  lt   3      return  n  gt  1   0  false  true  else if n 2    0    n 3    0      return false   int i   5   while i   i  lt   n       if n i    0     n  i 2     0           return false      i   i   6     return true     for any number  the minimum iterations to check if the number is prime or not can be from 2 to square root of the number  To reduce the iterations  even more  we can check if the number is divisible by 2 or 3 as maximum numbers can be eliminated by checking if the number is divisible by 2 or 3   Further any prime number greater than 3 can be expressed as 6k 1 or 6k-1  So the iteration can go from 6k 1 to the square root of the number

User · Answer

Way too late to the party  but hope this helps  This is relevant if you are looking for big primes   To test large odd numbers you need to use the Fermat-test and or Miller-Rabin test   These tests use modular exponentiation which is quite expensive  for n bits exponentiation you need at least n big int multiplication and n big int divison  Which means the complexity of modular exponentiation is O n      So before using the big guns  you need to do quite a few trial divisions  But don t do it naively  there is a way to do them fast  First multiply as many primes together as many fits into a the words you use for the big integers  If you use 32 bit words  multiply 3 5 7 11 13 17 19 23 29 3234846615 and compute the greatest common divisor with the number you test using the Euclidean algorithm  After the first step the number is reduced below the word size and continue the algorithm without performing complete big integer divisions  If the GCD    1  that means one of the primes you multiplied together divides the number  so you have a proof it s not prime  Then continue with 31 37 41 43 47   95041567  and so on   Once you tested several hundred  or thousand  primes this way  you can do 40 rounds of Miller-Rabin test to confirm the number is prime  after 40 rounds you can be certain the number is prime there is only 2 -80 chance it s not  it s more likely your hardware malfunctions

User · Answer

Similar idea to the AKS algorithm which has been mentioned  public static boolean isPrime int n         if n    2    n    3  return true      if  n  amp  1      0    n   3    0  return false      int limit    int Math sqrt n    1      for int i   5  w   2  i  lt   limit  i    w  w   6 - w            if n   i    0  return false          numChecks              return true

User · Answer

The best method  in my opinion  is to use what s gone before   There are lists of the first N primes on the internet with N stretching up to at least fifty million  Download the files and use them  it s likely to be much faster than any other method you ll come up with   If you want an actual algorithm for making your own primes  Wikipedia has all sorts of good stuff on primes here  including links to the various methods for doing it  and prime testing here  both probability-based and fast-deterministic methods   There should be a concerted effort to find the first billion  or even more  primes and get them published on the net somewhere so people can stop doing this same job over and over and over and      -

User · Answer

There are many ways to do the primality test   There isn t really a data structure for you to query  If you have lots of numbers to test  you should probably run a probabilistic test since those are faster  and then follow it up 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

User · Answer

I think one of the fastest is my method that I made   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  lt  lt  number  lt  lt    is hard to classify   n    return        if  number    2    cout  lt  lt  number  lt  lt    is Prime   n    return        if  number    3    cout  lt  lt  number  lt  lt    is Prime   n    return            Tests Odd Ball Factors     if  number   2    0    cout  lt  lt  number  lt  lt    is not Prime   n    return        if  number   3    0    cout  lt  lt  number  lt  lt    is not Prime   n    return         while  i  lt   lim            if  number   i    0    cout  lt  lt  number  lt  lt    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  lt  lt  number  lt  lt    is Prime   n   return

User · Answer

here is the fastest way to do it  def divisors integer       result          i   2      j   integer 2     while i  lt   j           if integer   i    0              result append i              if i    integer  i                  result append integer  i          i    1         j   integer  i     if len result   gt  0          return sorted result      else          return f quot  integer  is prime quot

User · Answer

best algorithm for Primes number javascript   function isPrime num          if  num  lt   1  return false        else if  num  lt   3  return true        else if  num   2    0    num   3    0  return false        var i   5        while  i   i  lt   num            if  num   i    0    num    i   2     0  return false          i    6                return true

User · Answer

A prime number is any number that is only divisible by 1 and itself  All other numbers are called composite   The simplest way  of finding a prime number  is to check if the input number is a composite number       function isPrime number               Check if a number is composite         for  let i   2  i  lt  number  i                  if  number   i     0                    return false                                     Return true for prime numbers         return true          The program has to divide the value of number by all the whole numbers from 1 and up to the its value  If this number can be divided evenly not only by one and itself it is a composite number   The initial value of the variable i has to be 2 because both prime and composite numbers can be evenly divided by 1       for  let i   2  i  lt  number  i      Then i is less than number for the same reason  Both prime and composite numbers can be evenly divided by themselves  Therefore there is no reason to check it   Then we check whether the variable can be divided evenly by using the remainder operator       if  number   i     0            return false          If the remainder is zero it means that number can be divided evenly  hence being a composite number and returning false   If the entered number didn t meet the condition  it means it s a prime number and the function returns true

User · Answer

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   lt  2          print user in   is a prime number            return     else          print user in   is not a prime number            return main

User · Answer

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

User · Answer

Here s my take on the answer   def isprime num       return num  lt   3 or  num   1    6    0 or  num - 1    6    0   The function will return True if any of the properties below are True  Those properties mathematically define what a prime is    The number is less than or equal to 3 The number   1 is divisible by 6 The number - 1 is divisible by 6

User · Answer

Python 3   def is prime a       return a  gt  1 and all a   i for i in range 2  int a  0 5    1

User · Answer

public static boolean isPrime int number     if number  lt  2     return false   else if number    2    number    3          return true        else           for int i 2 i lt  number 2 i               if number i    0               return false             else if i  number 2                  return true              return false

User · Answer

Smallest memory  This isn t smallest  but is a step in the right direction   class PrimeDictionary       BitArray bits       public PrimeDictionary int n            bits   new BitArray n   1           for  int i   0  2   i   3  lt   n  i                  bits Set i  CheckPrimality 2   i   3                         public PrimeDictionary IEnumerable lt int gt  primes            bits   new BitArray primes Max             foreach var prime in primes Where p   gt  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             Of course  you have to specify the definition of CheckPrimality

User · Answer

Let me suggest you the perfect solution for 64 bit integers  Sorry to use C   You have not already specified it as python in your first post  I hope you can find a simple modPow function and analyze it easily  public static bool IsPrime ulong number        return number    2            true             BigInterger ModPow 2  number  number     2                 number  amp  1    0  amp  amp  BinarySearchInA001567 number     false                 false     public static bool BinarySearchInA001567 ulong number           Is number in list         todo  Binary Search in A001567  https   oeis org A001567  below 2   64        Only 2 35 Gigabytes as a text file http   www cecm sfu ca Pseudoprimes index-2-to-64 html

User · Answer

For large numbers you cannot simply naively check whether the candidate number N is divisible by none of the numbers less than sqrt N   There are much more scalable tests available  such as the Miller-Rabin primality test  Below you have implementation in python  def is prime x        quot  quot  quot Fast implementation fo Miller-Rabin primality test  guaranteed to be correct  quot  quot  quot      import math     def get sd x            quot  quot  quot Returns  s  int  d  int  for which x   d 2 s  quot  quot  quot          if not x  return 0  0         s   0         while 1              if x   2    0                  x    2                 s    1             else                  return s  x     if x  lt   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 s 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 s 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 probably you want to first test whether the candidate number is divisible by any of the primes smaller than  say 1000  before you call Miller-Rabin  This will help you filter out obvious non-primes such as 10444344345

User · Answer

One can use sympy    import sympy  sympy ntheory primetest isprime 33393939393929292929292911111111   True   From sympy docs  The first step is looking for trivial factors  which if found enables a quick return  Next  if the sieve is large enough  use bisection search on the sieve  For small numbers  a set of deterministic Miller-Rabin tests are performed with bases that are known to have no counterexamples in their range  Finally if the number is larger than 2 64  a strong BPSW test is performed  While this is a probable prime test and we believe counterexamples exist  there are no known counterexamples

User · Answer

I compared the efficiency of the most popular suggestions to determine if a number is prime  I used python 3 6 on ubuntu 17 10  I tested with numbers up to 100 000  you can test with bigger numbers using my code below    This first plot compares the functions  which are explained further down in my answer   showing that the last functions do not grow as fast as the first one when increasing the numbers     And in the second plot we can see that in case of prime numbers the time grows steadily  but non-prime numbers do not grow so fast in time  because most of them can be eliminated early on      Here are the functions I used    this answer and this answer suggested a construct using all     def is prime 1 n       return n  gt  1 and all n   i for i in range 2  int math sqrt n     1    This answer used some kind of while loop   def is prime 2 n       if n  lt   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  lt   n          if n   i    0              return False         i    w         w   6 - w      return True  This answer included a version with a for loop   def is prime 3 n       if n  lt   1          return False      if n   2    0 and n  gt  2          return False      for i in range 3  int math sqrt n     1  2           if n   i    0              return False      return True  And I mixed a few ideas from the other answers into a new one   def is prime 4 n       if n  lt   1             negative numbers  0 or 1         return False     if n  lt   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 to compare the variants   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 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  running the function compare functions n 10  6   numbers up to 1 000 000  I get this 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    ---------------------------------------------------------------------     I used the following script to plot the results   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    lt   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

User · Answer

bool isPrime int n           Corner cases     if  n  lt   1   return false      if  n  lt   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 lt  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

User · Answer

Most of previous answers are correct but here is one more way to test to see a number is prime number  As refresher  prime numbers are whole number greater than 1 whose only factors are 1 and itself  source   Solution   Typically you can build a loop and start testing your number to see if it s divisible by 1 2 3    up to the number you are testing    etc but to reduce the time to check  you can divide your number by half of the value of your number because a number cannot be exactly divisible by anything above half of it s value  Example if you want to see 100 is a prime number you can loop through up 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 s a prime number      else      print  it s not a prime

User · Answer

I have got a prime function which works until  2 61 -1 Here   from math import sqrt def isprime num   num  gt  1 and return all num   x for x in range 2  int sqrt num  1      Explanation   The all   function can be redefined to this   def all variables       for element in variables          if not element  return False     return True   The all   function just goes through a series of bools   numbers and returns False if it sees 0 or False   The sqrt   function is just doing the square root of a number   For example    gt  gt  gt  from math import sqrt  gt  gt  gt  sqrt 9   gt  gt  gt  3  gt  gt  gt  sqrt 100   gt  gt  gt  10   The num   x part returns the remainder of num   x   Finally  range 2  int sqrt num    means that it will create a list that  starts at 2 and ends at int sqrt num  1   For more information about range  have a look at this website   The num  gt  1 part is just checking if the variable num is larger than 1  becuase 1 and 0 are not considered prime numbers   I hope this helped

User · Answer

In Python 3   def is prime a       if a  lt  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 only divisible by itself and 1  Ex  2 3 5 7     1  if a lt 2  if  a  is less than 2 it is not a prime   2  elif a  2 and a   2    0  if  a  is divisible by 2 then its definitely not a prime  But if a 2 we don t want to evaluate that as it is a prime number  Hence the condition a  2  3  return all  a   i for i in range 3  int a0 5  1       First look at what all   command does in python   Starting from 3 we divide  a  till its square root  a  0 5   If  a  is divisible the output will be False   Why square root  Let s say a 16  The square root of 16   4  We don t need to evaluate till 15  We only need to check till 4 to say that it s not a prime    Extra  A loop for finding all the prime number within a range   for i in range 1 100       if is prime i           print     is a prime number  format i

User · Answer

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 would use all n   p    0       but that requires strict evaluation of all values of p  The not any version can terminate early if a True value is found

User · Answer

When I have to do a fast verification  I write this simple code based on the basic division between numbers lower than square root of input  def isprime n       if n 2  0          return n  2     else          cota   int n  0 5  1         for ind in range 3 2 cota               if n ind  0                  print ind                  return False     is one   n  1     return True    is one  isprime 22783    The last True    n  1 is to avoid the case n 1

User · Answer

The fastest algorithm for general prime testing is AKS  The Wikipedia article describes it at lengths and links to the original paper   If you want to find big numbers  look into primes that have special forms like Mersenne primes   The algorithm 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  lt   n          if n   i    0              return False          i    w         w   6 - w      return True   It s a variant of the classic O sqrt N   algorithm  It uses the fact that a prime  except 2 and 3  is of form 6k - 1 or 6k   1 and looks only at divisors of this form   Sometimes  If I really want speed and the range is limited  I implement a pseudo-prime test based on Fermat s little theorem  If I really want more speed  i e  avoid O sqrt N   algorithm altogether   I precompute the false positives  see Carmichael numbers  and do a binary search  This is by far the fastest test I ve ever implemented  the only drawback is that the range is limited

User · Answer

With help of Java-8 streams and lambdas  it can be implemented like this in just few lines   public static boolean isPrime int candidate           int candidateRoot    int  Math sqrt   double  candidate           return IntStream range 2 candidateRoot                   boxed   noneMatch x - gt  candidate   x    0           Performance should be close to O sqrt N    Maybe someone find it useful

User · Answer

First Rule of a Prime  If divided by 2 equals a whole number or integer No its not prime    Fastest method to Know using any computer language is type matching using strings not math  Match the DOT in a stringed Float    Divide it by 2    n   n   2 Convert this to a string    n   string n  if     in n       printf  Yes I Am Prime

User · Answer

myInp int input  Enter a number      if myInp  1      print  The number    is neither a prime not composite no  format myInp   elif myInp gt 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

User · Answer

According to wikipedia  the Sieve of Eratosthenes has complexity O n    log n     log log n   and requires O n  memory - so it s a pretty good place to start if you aren t testing for especially large numbers

User · Answer

We can use java streams to implement this in O sqrt n    Consider that noneMatch is a shortCircuiting method that stops the operation when finds it unnecessary for determining 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 - gt  n   a    0     Prime     Not Prime

User · Answer

To find if the number or numbers in a range is are prime    usr bin python3  def prime check  args       for arg in args          if arg  gt  1        prime numbers are greater than 1             for i in range 2 arg       check for factors                 if arg   i     0                      print arg  quot is not Prime quot                       print i  quot times quot  arg  i  quot is quot  arg                      break             else                  print arg  quot is Prime quot                                  if input number is less than               or equal to 1  it is not prime         else              print arg  quot is not Prime quot       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

[algorithm] How to create the most compact mapping n ? isprime(n) up to a limit N?

Examples related to algorithm

Examples related to math

Examples related to data-structures

Examples related to primes