Which is the fastest algorithm to find prime numbers

Question

Which is the fastest algorithm to find out prime numbers using C    I have used sieve s algorithm but I still want it to be faster

User · Answer

If it has to be really fast you can include a list of primes:
http://www.bigprimes.net/archive/prime/

If you just have to know if a certain number is a prime number, there are various prime tests listed on wikipedia. They are probably the fastest method to determine if large numbers are primes, especially because they can tell you if a number is not a prime.

User · Answer

I will let you decide if it s the fastest or not   using System  namespace PrimeNumbers    public static class Program       static int primesCount   0        public static void Main                 DateTime startingTime   DateTime Now           RangePrime 1 1000000               DateTime endingTime   DateTime Now           TimeSpan span   endingTime - startingTime           Console WriteLine  span    0    span TotalSeconds                public static void RangePrime int start  int end                for  int i   start  i    end 1  i                          bool isPrime   IsPrime i               if isPrime                                primesCount                    Console WriteLine  number    0    i                                   Console WriteLine  primes count    0   primesCount                public static bool IsPrime int ToCheck                 if  ToCheck    2  return true          if  ToCheck  lt  2  return false            if  IsOdd ToCheck                         for  int i   3  i  lt    ToCheck   3   i    2                                if  ToCheck   i    0  return false                            return true                    else return false     even numbers excluding 2  are composite            public static bool IsOdd int ToCheck                return   ToCheck   2    0    true   false               It takes approximately 82 seconds to find and print prime numbers within a range of 1 to 1 000 000  on my Core 2 Duo laptop with a 2 40 GHz processor  And it found 78 498 prime numbers

User · Answer

If it has to be really fast you can include a list of primes:
http://www.bigprimes.net/archive/prime/

If you just have to know if a certain number is a prime number, there are various prime tests listed on wikipedia. They are probably the fastest method to determine if large numbers are primes, especially because they can tell you if a number is not a prime.

User · Answer

Is your problem to decide whether a particular number is prime  Then you need a primality test  easy   Or do you need all primes up to a given number  In that case prime sieves are good  easy  but require memory   Or do you need the prime factors of a number  This would require factorization  difficult for large numbers if you really want the most efficient methods   How large are the numbers you are looking at  16 bits  32 bits  bigger   One clever and efficient way is to pre-compute tables of primes and keep them in a file using a bit-level encoding  The file is considered one long bit vector whereas bit n represents integer n  If n is prime  its bit is set to one and to zero otherwise  Lookup is very fast  you compute the byte offset and a bit mask  and does not require loading the file in memory

User · Answer

A very fast implementation of the Sieve of Atkin is Dan Bernstein s primegen  This sieve is more efficient than the Sieve of Eratosthenes  His page has some benchmark information

User · Answer

It depends on your application   There are some considerations    Do you need just the information whether a few numbers are prime  do you need all prime numbers up to a certain limit  or do you need  potentially  all prime numbers  How big are the numbers you have to deal with    The Miller-Rabin and analogue tests are only faster than a sieve for numbers over a certain size  somewhere around a few million  I believe    Below that  using a trial division  if you just have a few numbers  or a sieve is faster

User · Answer

He  he I know I m a question necromancer replying to old questions  but I ve just found this question searching the net for ways to implement efficient prime numbers tests   Until now  I believe that the fastest prime number testing algorithm is  Strong Probable Prime  SPRP   I am quoting from Nvidia CUDA forums       One of the more practical niche problems in number theory has to do   with identification of prime numbers  Given N  how can you efficiently   determine if it is prime or not  This is not just a thoeretical   problem  it may be a real one needed in code  perhaps when you need to   dynamically find a prime hash table size within certain ranges  If N   is something on the order of 2 30  do you really want to do 30000   division tests to search for any factors  Obviously not       The common practical solution to this problem is a simple test called   an Euler probable prime test  and a more powerful generalization   called a Strong Probable Prime  SPRP   This is a test that for an   integer N can probabilistically classify it as prime or not  and   repeated tests can increase the correctness probability  The slow part   of the test itself mostly involves computing a value similar to   A  N-1  modulo N  Anyone implementing RSA public-key encryption   variants has used this algorithm  It s useful both for huge integers    like 512 bits  as well as normal 32 or 64 bit ints       The test can be changed from a probabilistic rejection into a   definitive proof of primality by precomputing certain test input   parameters which are known to always succeed for ranges of N    Unfortunately the discovery of these  best known tests  is effectively   a search of a huge  in fact infinite  domain  In 1980  a first list of   useful tests was created by Carl Pomerance  famous for being the one   to factor RSA-129 with his Quadratic Seive algorithm   Later Jaeschke   improved the results significantly in 1993  In 2004  Zhang and Tang   improved the theory and limits of the search domain  Greathouse and   Livingstone have released the most modern results until now on the   web  at http   math crg4 com primes html  the best results of a huge   search domain    See here for more info  http   primes utm edu prove prove2 3 html and http   forums nvidia com index php showtopic 70483  If you just need a way to generate very big prime numbers and don t care to generate all prime numbers  lt  an integer n  you can use Lucas-Lehmer test to verify Mersenne prime numbers  A Mersenne prime number is in the form of 2 p -1  I think that Lucas-Lehmer test is the fastest algorithm discovered for Mersenne prime numbers   And if you not only want to use the fastest algorithm but also the fastest hardware  try to implement it using Nvidia CUDA  write a kernel for CUDA and run it on GPU   You can even earn some money if you discover large enough prime numbers  EFF is giving prizes from  50K to  250K   https   www eff org awards coop

User · Answer

A very fast implementation of the Sieve of Atkin is Dan Bernstein s primegen  This sieve is more efficient than the Sieve of Eratosthenes  His page has some benchmark information

User · Answer

If it has to be really fast you can include a list of primes:
http://www.bigprimes.net/archive/prime/

If you just have to know if a certain number is a prime number, there are various prime tests listed on wikipedia. They are probably the fastest method to determine if large numbers are primes, especially because they can tell you if a number is not a prime.

User · Answer

Rabin-Miller is a standard probabilistic primality test   you run it K times and the input number is either definitely composite  or it is probably prime with probability of error 4-K   a few hundred iterations and it s almost certainly telling you the truth   There is a non-probabilistic  deterministic  variant of Rabin Miller    The Great Internet Mersenne Prime Search  GIMPS  which has found the world s record for largest proven prime  274 207 281 - 1 as of June 2017   uses several algorithms  but these are primes in special forms  However the GIMPS page above does include some general deterministic primality tests  They appear to indicate that which algorithm is  fastest  depends upon the size of the number to be tested  If your number fits in 64 bits then you probably shouldn t use a method intended to work on primes of several million digits

User · Answer

include  lt stdio h gt   int main     works for first 10000 primes     define LEAST PRIME 2  int remainder  number to be checked   LEAST PRIME  divisor   2  remainder dump   upper limit    upper limit to be specified by user  int i   1  printf  quot             SPECIFY UPPER LIMIT     quot    scanf  quot  d quot    amp upper limit   printf  quot 1  2  n quot   number to be checked     PRINTS 2  do       remainder dump   1      divisor   2       do               remainder   number to be checked   divisor          if  remainder    0                        remainder dump   remainder dump   remainder     dumping 0 for rejection                      divisor         while  divisor  lt   number to be checked divisor      upto here we know number is prime or  not      if  remainder dump    0                  i          printf  quot  d    d  t quot   i  number to be checked     print if prime             number to be checked   number to be checked   1    while  number to be checked  lt   upper limit   printf  quot  nNUMBER OF PRIMES             t d quot   i    return 0     This can indefinitely list prime numbers  Sorry for length I wrote this program when I was just 3 days into programming so it uses very basic functions  After the edit suggested in the comment section it prints prime upto 1 000 000 in 13 secs

User · Answer

I know it s somewhat later  but this could be useful to people arriving here from searches  Anyway  here s some JavaScript that relies on the fact that only prime factors need to be tested  so the earlier primes generated by the code are re-used as test factors for later ones  Of course  all even and mod 5 values are filtered out first  The result will be in the array P  and this code can crunch 10 million primes in under 1 5 seconds on an i7 PC  or 100 million in about 20   Rewritten in C it should be very fast   var P    1  2   j  k  l   3  for  k   3   k  lt  10000000   k    2      loop  if    l  lt  5          for  j   2   P j   lt   Math sqrt k      j        if  k   P j     0  break loop      P P length    k       else l   0

User · Answer

It depends on your application   There are some considerations    Do you need just the information whether a few numbers are prime  do you need all prime numbers up to a certain limit  or do you need  potentially  all prime numbers  How big are the numbers you have to deal with    The Miller-Rabin and analogue tests are only faster than a sieve for numbers over a certain size  somewhere around a few million  I believe    Below that  using a trial division  if you just have a few numbers  or a sieve is faster

User · Answer

I know it s somewhat later  but this could be useful to people arriving here from searches  Anyway  here s some JavaScript that relies on the fact that only prime factors need to be tested  so the earlier primes generated by the code are re-used as test factors for later ones  Of course  all even and mod 5 values are filtered out first  The result will be in the array P  and this code can crunch 10 million primes in under 1 5 seconds on an i7 PC  or 100 million in about 20   Rewritten in C it should be very fast   var P    1  2   j  k  l   3  for  k   3   k  lt  10000000   k    2      loop  if    l  lt  5          for  j   2   P j   lt   Math sqrt k      j        if  k   P j     0  break loop      P P length    k       else l   0

User · Answer

u can try this code  fastest way to get prime with the less loop posible a number like 1000 will get less than 15 loops 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    print divisors 1827   print divisors 1025   print divisors 27

User · Answer

A very fast implementation of the Sieve of Atkin is Dan Bernstein s primegen  This sieve is more efficient than the Sieve of Eratosthenes  His page has some benchmark information

User · Answer

It depends on your application   There are some considerations    Do you need just the information whether a few numbers are prime  do you need all prime numbers up to a certain limit  or do you need  potentially  all prime numbers  How big are the numbers you have to deal with    The Miller-Rabin and analogue tests are only faster than a sieve for numbers over a certain size  somewhere around a few million  I believe    Below that  using a trial division  if you just have a few numbers  or a sieve is faster

User · Answer

I always use this method for calculating primes numbers following with the sieve algorithm    void primelist         for int i   4  i  lt  pr  i    2  mark  i     false     for int i   3  i  lt  pr  i    2  mark  i     true  mark  2     true     for int i   3  sq   sqrt  pr    i  lt  sq  i    2         if mark  i              for int j   i  lt  lt  1  j  lt  pr  j    i  mark  j     false    prime  0     2  ind   1    for int i   3  i  lt  pr  i    2      if mark  i    ind    printf   d n   ind

User · Answer

include  lt iostream gt   using namespace std   int set  1000000    int main          for  int i 0  i lt 1000000  i             set  i    0            int set size  1000      set  set size       set  0    2      set  1    3      int Ps   0      int last   2       cout  lt  lt  2  lt  lt       lt  lt  3  lt  lt            for  int n 1  n lt 10000  n             int t   0          Ps    n 2  1  3 n           for  int i 0  i  i  i                 if  set  i     0  break              if  Ps set i   0                   t 1                  break                                  if  t  0               cout  lt  lt  Ps  lt  lt                   set  last    Ps              last                          cout  lt  lt  last  lt  lt  endl        cout  lt  lt  endl       system   pause        return 0

User · Answer

I will let you decide if it s the fastest or not   using System  namespace PrimeNumbers    public static class Program       static int primesCount   0        public static void Main                 DateTime startingTime   DateTime Now           RangePrime 1 1000000               DateTime endingTime   DateTime Now           TimeSpan span   endingTime - startingTime           Console WriteLine  span    0    span TotalSeconds                public static void RangePrime int start  int end                for  int i   start  i    end 1  i                          bool isPrime   IsPrime i               if isPrime                                primesCount                    Console WriteLine  number    0    i                                   Console WriteLine  primes count    0   primesCount                public static bool IsPrime int ToCheck                 if  ToCheck    2  return true          if  ToCheck  lt  2  return false            if  IsOdd ToCheck                         for  int i   3  i  lt    ToCheck   3   i    2                                if  ToCheck   i    0  return false                            return true                    else return false     even numbers excluding 2  are composite            public static bool IsOdd int ToCheck                return   ToCheck   2    0    true   false               It takes approximately 82 seconds to find and print prime numbers within a range of 1 to 1 000 000  on my Core 2 Duo laptop with a 2 40 GHz processor  And it found 78 498 prime numbers

User · Answer

He  he I know I m a question necromancer replying to old questions  but I ve just found this question searching the net for ways to implement efficient prime numbers tests   Until now  I believe that the fastest prime number testing algorithm is  Strong Probable Prime  SPRP   I am quoting from Nvidia CUDA forums       One of the more practical niche problems in number theory has to do   with identification of prime numbers  Given N  how can you efficiently   determine if it is prime or not  This is not just a thoeretical   problem  it may be a real one needed in code  perhaps when you need to   dynamically find a prime hash table size within certain ranges  If N   is something on the order of 2 30  do you really want to do 30000   division tests to search for any factors  Obviously not       The common practical solution to this problem is a simple test called   an Euler probable prime test  and a more powerful generalization   called a Strong Probable Prime  SPRP   This is a test that for an   integer N can probabilistically classify it as prime or not  and   repeated tests can increase the correctness probability  The slow part   of the test itself mostly involves computing a value similar to   A  N-1  modulo N  Anyone implementing RSA public-key encryption   variants has used this algorithm  It s useful both for huge integers    like 512 bits  as well as normal 32 or 64 bit ints       The test can be changed from a probabilistic rejection into a   definitive proof of primality by precomputing certain test input   parameters which are known to always succeed for ranges of N    Unfortunately the discovery of these  best known tests  is effectively   a search of a huge  in fact infinite  domain  In 1980  a first list of   useful tests was created by Carl Pomerance  famous for being the one   to factor RSA-129 with his Quadratic Seive algorithm   Later Jaeschke   improved the results significantly in 1993  In 2004  Zhang and Tang   improved the theory and limits of the search domain  Greathouse and   Livingstone have released the most modern results until now on the   web  at http   math crg4 com primes html  the best results of a huge   search domain    See here for more info  http   primes utm edu prove prove2 3 html and http   forums nvidia com index php showtopic 70483  If you just need a way to generate very big prime numbers and don t care to generate all prime numbers  lt  an integer n  you can use Lucas-Lehmer test to verify Mersenne prime numbers  A Mersenne prime number is in the form of 2 p -1  I think that Lucas-Lehmer test is the fastest algorithm discovered for Mersenne prime numbers   And if you not only want to use the fastest algorithm but also the fastest hardware  try to implement it using Nvidia CUDA  write a kernel for CUDA and run it on GPU   You can even earn some money if you discover large enough prime numbers  EFF is giving prizes from  50K to  250K   https   www eff org awards coop

User · Answer

i wrote it today in C compiled with tcc  figured out during preparation of compititive exams several years back  don t know if anyone already have wrote it alredy  it really fast but you should decide whether it is fast or not   took one or two minuts to findout about 1 00 004 prime numbers between 10 and 1 00 00 000 on i7 processor with average 32  CPU use  as you know  only those can be prime which have last digit either 1 3 7 or 9 and to check if that number is prime or not  you have to divide that number by previously found prime numbers only  so first take group of four number    1 3 7 9   test it by dividing by known prime numbers  if reminder is  non zero then number is prime  add it to prime number array  then add 10 to group so it becomes  11 13 17 19  and repeat the process   include  lt stdio h gt  int main             int nums 4   1 3 7 9       int primes 100000       primes 0  2      primes 1  3      primes 2  5      primes 3  7      int found   4      int got   1      int m 0      int upto   1000000      for int i 0 i lt upto i               printf  quot iteration number   d n quot  i           for int j 0 j lt 4 j                 m   nums j  10                printf  quot m    d n quot  m               nums j    m              got   1              for int k 0 k lt found k                       printf  quot testing with  d n quot  primes k                    if m primes k   0                       got   0                        printf  quot  d failed for  d n quot  m primes k                        break                                              if got  1                     printf  quot got new prime   d n quot  m                   primes found   m                  found                                      printf  quot found total  d prime numbers between 1 and  d quot  found upto 10       return 0

User · Answer

It depends on your application   There are some considerations    Do you need just the information whether a few numbers are prime  do you need all prime numbers up to a certain limit  or do you need  potentially  all prime numbers  How big are the numbers you have to deal with    The Miller-Rabin and analogue tests are only faster than a sieve for numbers over a certain size  somewhere around a few million  I believe    Below that  using a trial division  if you just have a few numbers  or a sieve is faster

User · Answer

include  lt stdio h gt   int main     works for first 10000 primes     define LEAST PRIME 2  int remainder  number to be checked   LEAST PRIME  divisor   2  remainder dump   upper limit    upper limit to be specified by user  int i   1  printf  quot             SPECIFY UPPER LIMIT     quot    scanf  quot  d quot    amp upper limit   printf  quot 1  2  n quot   number to be checked     PRINTS 2  do       remainder dump   1      divisor   2       do               remainder   number to be checked   divisor          if  remainder    0                        remainder dump   remainder dump   remainder     dumping 0 for rejection                      divisor         while  divisor  lt   number to be checked divisor      upto here we know number is prime or  not      if  remainder dump    0                  i          printf  quot  d    d  t quot   i  number to be checked     print if prime             number to be checked   number to be checked   1    while  number to be checked  lt   upper limit   printf  quot  nNUMBER OF PRIMES             t d quot   i    return 0     This can indefinitely list prime numbers  Sorry for length I wrote this program when I was just 3 days into programming so it uses very basic functions  After the edit suggested in the comment section it prints prime upto 1 000 000 in 13 secs

User · Answer

Rabin-Miller is a standard probabilistic primality test   you run it K times and the input number is either definitely composite  or it is probably prime with probability of error 4-K   a few hundred iterations and it s almost certainly telling you the truth   There is a non-probabilistic  deterministic  variant of Rabin Miller    The Great Internet Mersenne Prime Search  GIMPS  which has found the world s record for largest proven prime  274 207 281 - 1 as of June 2017   uses several algorithms  but these are primes in special forms  However the GIMPS page above does include some general deterministic primality tests  They appear to indicate that which algorithm is  fastest  depends upon the size of the number to be tested  If your number fits in 64 bits then you probably shouldn t use a method intended to work on primes of several million digits

User · Answer

A very fast implementation of the Sieve of Atkin is Dan Bernstein s primegen  This sieve is more efficient than the Sieve of Eratosthenes  His page has some benchmark information

User · Answer

include lt iostream gt  using namespace std   void main         int num i j prime      cout lt  lt  Enter the upper limit         cin gt  gt num       cout lt  lt  Prime numbers till   lt  lt num lt  lt   are  2          for i 3 i lt  num i                  prime 1          for j 2 j lt i j                          if i j  0                                prime 0                  break                                   if prime  1              cout lt  lt i lt  lt

User · Answer

I recently wrote this code to find the sum of numbers  It can be easily modified to find if a number is prime or not instead   Benchmarks are on top of the code     built on core-i2 e8400    Benchmark from PowerShell    Measure-Command   ExeName exe      Days                0    Hours               0    Minutes             0    Seconds             23    Milliseconds        516    Ticks               235162598    TotalDays           0 00027217893287037    TotalHours          0 00653229438888889    TotalMinutes        0 391937663333333    TotalSeconds        23 5162598    TotalMilliseconds   23516 2598    built with latest MSVC    cl  EHsc  std c  latest main cpp  O2  fp fast  Qpar   include  lt cmath gt   include  lt iostream gt   include  lt vector gt   inline auto prime      std  uint64 t I  std  vector lt std  uint64 t gt   amp cache  - gt  std  uint64 t       std  uint64 t root static cast lt std  uint64 t gt  std  sqrtl I         for  std  size t i    cache i   lt   root    i          if  I   cache i     0              return 0       cache push back I       return I      inline auto prime sum      std  uint64 t S  - gt  std  uint64 t       std  uint64 t R 5       std  vector lt std  uint64 t gt  cache      cache reserve S   16       cache push back 3        for  std  uint64 t I 5   I  lt   S  I    8                std  uint64 t U I   3           if  U    0              R    prime I  cache           if  U    1              R    prime I   2  cache           if  U    2              R    prime I   4  cache           R    prime I   6  cache             return R      int main         std  cout  lt  lt  prime sum 63210123

User · Answer

There is a 100  mathematical test that will check if a number P is prime or composite  called AKS Primality Test    The concept is simple  given a number P  if all the coefficients of  x-1  P -  x P-1  are divisible by P  then P is a prime number  otherwise it is a composite number    For instance  given P   3  would give the polynomial       x-1  3 -  x 3 - 1     x 3   3x 2 - 3x - 1 -  x 3 - 1     3x 2 - 3x   And the coefficients are both divisible by 3  therefore the number is prime    And example where P   4  which is NOT a prime would yield       x-1  4 -  x 4-1     x 4 - 4x 3   6x 2 - 4x   1 -  x 4 - 1     -4x 3   6x 2 - 4x   And here we can see that the coefficients 6 is not divisible by 4  therefore it is NOT prime   The polynomial  x-1  P will P 1 terms and can be found using combination  So  this test will run in O n  runtime  so I don t know how useful this would be since you can simply iterate over i from 0 to p and test for the remainder

User · Answer

include lt iostream gt  using namespace std   void main         int num i j prime      cout lt  lt  Enter the upper limit         cin gt  gt num       cout lt  lt  Prime numbers till   lt  lt num lt  lt   are  2          for i 3 i lt  num i                  prime 1          for j 2 j lt i j                          if i j  0                                prime 0                  break                                   if prime  1              cout lt  lt i lt  lt

User · Answer

Rabin-Miller is a standard probabilistic primality test   you run it K times and the input number is either definitely composite  or it is probably prime with probability of error 4-K   a few hundred iterations and it s almost certainly telling you the truth   There is a non-probabilistic  deterministic  variant of Rabin Miller    The Great Internet Mersenne Prime Search  GIMPS  which has found the world s record for largest proven prime  274 207 281 - 1 as of June 2017   uses several algorithms  but these are primes in special forms  However the GIMPS page above does include some general deterministic primality tests  They appear to indicate that which algorithm is  fastest  depends upon the size of the number to be tested  If your number fits in 64 bits then you probably shouldn t use a method intended to work on primes of several million digits

User · Answer

include lt stdio h gt  main         long long unsigned x y b z e r c      scanf   llu   amp x       if x lt 2 return 0      scanf   llu   amp y       if y lt x return 0      if x  2 printf   2        if x 2  0 x  1      if y 2  0 y- 1      for b x b lt  y b  2                z b e 0          for c 2 c c lt  z c                          if z c  0 e                if e gt 0 z 3                    if e  0                        printf    llu  z               r  1                      printf    n llu outputs    n  r       scanf   llu   amp r

User · Answer

I recently wrote this code to find the sum of numbers  It can be easily modified to find if a number is prime or not instead   Benchmarks are on top of the code     built on core-i2 e8400    Benchmark from PowerShell    Measure-Command   ExeName exe      Days                0    Hours               0    Minutes             0    Seconds             23    Milliseconds        516    Ticks               235162598    TotalDays           0 00027217893287037    TotalHours          0 00653229438888889    TotalMinutes        0 391937663333333    TotalSeconds        23 5162598    TotalMilliseconds   23516 2598    built with latest MSVC    cl  EHsc  std c  latest main cpp  O2  fp fast  Qpar   include  lt cmath gt   include  lt iostream gt   include  lt vector gt   inline auto prime      std  uint64 t I  std  vector lt std  uint64 t gt   amp cache  - gt  std  uint64 t       std  uint64 t root static cast lt std  uint64 t gt  std  sqrtl I         for  std  size t i    cache i   lt   root    i          if  I   cache i     0              return 0       cache push back I       return I      inline auto prime sum      std  uint64 t S  - gt  std  uint64 t       std  uint64 t R 5       std  vector lt std  uint64 t gt  cache      cache reserve S   16       cache push back 3        for  std  uint64 t I 5   I  lt   S  I    8                std  uint64 t U I   3           if  U    0              R    prime I  cache           if  U    1              R    prime I   2  cache           if  U    2              R    prime I   4  cache           R    prime I   6  cache             return R      int main         std  cout  lt  lt  prime sum 63210123

User · Answer

i wrote it today in C compiled with tcc  figured out during preparation of compititive exams several years back  don t know if anyone already have wrote it alredy  it really fast but you should decide whether it is fast or not   took one or two minuts to findout about 1 00 004 prime numbers between 10 and 1 00 00 000 on i7 processor with average 32  CPU use  as you know  only those can be prime which have last digit either 1 3 7 or 9 and to check if that number is prime or not  you have to divide that number by previously found prime numbers only  so first take group of four number    1 3 7 9   test it by dividing by known prime numbers  if reminder is  non zero then number is prime  add it to prime number array  then add 10 to group so it becomes  11 13 17 19  and repeat the process   include  lt stdio h gt  int main             int nums 4   1 3 7 9       int primes 100000       primes 0  2      primes 1  3      primes 2  5      primes 3  7      int found   4      int got   1      int m 0      int upto   1000000      for int i 0 i lt upto i               printf  quot iteration number   d n quot  i           for int j 0 j lt 4 j                 m   nums j  10                printf  quot m    d n quot  m               nums j    m              got   1              for int k 0 k lt found k                       printf  quot testing with  d n quot  primes k                    if m primes k   0                       got   0                        printf  quot  d failed for  d n quot  m primes k                        break                                              if got  1                     printf  quot got new prime   d n quot  m                   primes found   m                  found                                      printf  quot found total  d prime numbers between 1 and  d quot  found upto 10       return 0

User · Answer

Is your problem to decide whether a particular number is prime  Then you need a primality test  easy   Or do you need all primes up to a given number  In that case prime sieves are good  easy  but require memory   Or do you need the prime factors of a number  This would require factorization  difficult for large numbers if you really want the most efficient methods   How large are the numbers you are looking at  16 bits  32 bits  bigger   One clever and efficient way is to pre-compute tables of primes and keep them in a file using a bit-level encoding  The file is considered one long bit vector whereas bit n represents integer n  If n is prime  its bit is set to one and to zero otherwise  Lookup is very fast  you compute the byte offset and a bit mask  and does not require loading the file in memory

User · Answer

Rabin-Miller is a standard probabilistic primality test   you run it K times and the input number is either definitely composite  or it is probably prime with probability of error 4-K   a few hundred iterations and it s almost certainly telling you the truth   There is a non-probabilistic  deterministic  variant of Rabin Miller    The Great Internet Mersenne Prime Search  GIMPS  which has found the world s record for largest proven prime  274 207 281 - 1 as of June 2017   uses several algorithms  but these are primes in special forms  However the GIMPS page above does include some general deterministic primality tests  They appear to indicate that which algorithm is  fastest  depends upon the size of the number to be tested  If your number fits in 64 bits then you probably shouldn t use a method intended to work on primes of several million digits

User · Answer

There is a 100  mathematical test that will check if a number P is prime or composite  called AKS Primality Test    The concept is simple  given a number P  if all the coefficients of  x-1  P -  x P-1  are divisible by P  then P is a prime number  otherwise it is a composite number    For instance  given P   3  would give the polynomial       x-1  3 -  x 3 - 1     x 3   3x 2 - 3x - 1 -  x 3 - 1     3x 2 - 3x   And the coefficients are both divisible by 3  therefore the number is prime    And example where P   4  which is NOT a prime would yield       x-1  4 -  x 4-1     x 4 - 4x 3   6x 2 - 4x   1 -  x 4 - 1     -4x 3   6x 2 - 4x   And here we can see that the coefficients 6 is not divisible by 4  therefore it is NOT prime   The polynomial  x-1  P will P 1 terms and can be found using combination  So  this test will run in O n  runtime  so I don t know how useful this would be since you can simply iterate over i from 0 to p and test for the remainder

User · Answer

If it has to be really fast you can include a list of primes:
http://www.bigprimes.net/archive/prime/

If you just have to know if a certain number is a prime number, there are various prime tests listed on wikipedia. They are probably the fastest method to determine if large numbers are primes, especially because they can tell you if a number is not a prime.

User · Answer

Is your problem to decide whether a particular number is prime  Then you need a primality test  easy   Or do you need all primes up to a given number  In that case prime sieves are good  easy  but require memory   Or do you need the prime factors of a number  This would require factorization  difficult for large numbers if you really want the most efficient methods   How large are the numbers you are looking at  16 bits  32 bits  bigger   One clever and efficient way is to pre-compute tables of primes and keep them in a file using a bit-level encoding  The file is considered one long bit vector whereas bit n represents integer n  If n is prime  its bit is set to one and to zero otherwise  Lookup is very fast  you compute the byte offset and a bit mask  and does not require loading the file in memory

User · Answer

include  lt iostream gt   using namespace std   int set  1000000    int main          for  int i 0  i lt 1000000  i             set  i    0            int set size  1000      set  set size       set  0    2      set  1    3      int Ps   0      int last   2       cout  lt  lt  2  lt  lt       lt  lt  3  lt  lt            for  int n 1  n lt 10000  n             int t   0          Ps    n 2  1  3 n           for  int i 0  i  i  i                 if  set  i     0  break              if  Ps set i   0                   t 1                  break                                  if  t  0               cout  lt  lt  Ps  lt  lt                   set  last    Ps              last                          cout  lt  lt  last  lt  lt  endl        cout  lt  lt  endl       system   pause        return 0

User · Answer

I always use this method for calculating primes numbers following with the sieve algorithm    void primelist         for int i   4  i  lt  pr  i    2  mark  i     false     for int i   3  i  lt  pr  i    2  mark  i     true  mark  2     true     for int i   3  sq   sqrt  pr    i  lt  sq  i    2         if mark  i              for int j   i  lt  lt  1  j  lt  pr  j    i  mark  j     false    prime  0     2  ind   1    for int i   3  i  lt  pr  i    2      if mark  i    ind    printf   d n   ind

User · Answer

u can try this code  fastest way to get prime with the less loop posible a number like 1000 will get less than 15 loops 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    print divisors 1827   print divisors 1025   print divisors 27

User · Answer

Is your problem to decide whether a particular number is prime  Then you need a primality test  easy   Or do you need all primes up to a given number  In that case prime sieves are good  easy  but require memory   Or do you need the prime factors of a number  This would require factorization  difficult for large numbers if you really want the most efficient methods   How large are the numbers you are looking at  16 bits  32 bits  bigger   One clever and efficient way is to pre-compute tables of primes and keep them in a file using a bit-level encoding  The file is considered one long bit vector whereas bit n represents integer n  If n is prime  its bit is set to one and to zero otherwise  Lookup is very fast  you compute the byte offset and a bit mask  and does not require loading the file in memory

User · Answer

include lt stdio h gt  main         long long unsigned x y b z e r c      scanf   llu   amp x       if x lt 2 return 0      scanf   llu   amp y       if y lt x return 0      if x  2 printf   2        if x 2  0 x  1      if y 2  0 y- 1      for b x b lt  y b  2                z b e 0          for c 2 c c lt  z c                          if z c  0 e                if e gt 0 z 3                    if e  0                        printf    llu  z               r  1                      printf    n llu outputs    n  r       scanf   llu   amp r

[c++] Which is the fastest algorithm to find prime numbers?

Examples related to c++

Examples related to algorithm

Examples related to primes