Calculating and printing the nth prime number

Question

I am trying to calculate prime numbers  which I ve already done  But I want to calculate and print ONLY the nth prime number  User input   while calculating the rest  They won t be printed  only the nth prime number will be printed   Here s what I ve written so far   import java util Scanner         Calculates the nth prime number     author  Zyst      public class Prime       public static void main String   args             Scanner input   new Scanner System in           int n               i   2               x   2           System out printf  This program calculates the nth Prime number n            System out printf  Please enter the nth prime number you want to find              n   input nextInt             for i   2  x   2  i  lt   n  i                  for x   2  x  lt  i  x                      if i   x    0                        break                                              if x    i                    System out printf   n d is prime   x                                     This is the program I wrote to calculate the prime numbers from 1 to n  However  I want it to only print the nth prime number   What I ve thought of doing is making some sort of count int and   ing it every time it finds a prime  and when the count    n then it prints out that number  but I can t quite figure out how to land it

User · Answer

This program is an efficient one   I have added one more check-in if to get the square root of a number and check is it divisible or not if it s then its not a prime number  this will solve all the problems efficiently    public static void main String   args                 Scanner sc   new Scanner System in           int T     number of test cases         T   sc nextInt            long   number   new long T           if 1 lt   T  amp  amp  T  lt   30           for int i  0 i lt T i                 number i  sc nextInt       read all the numbers                   for int i  0 i lt T i                 if isPrime number i                    System out println  Prime                else                System out println  Not prime                            else       return               is prime or not     static boolean isPrime long num           if num  1            return false          if num  lt   3            return true          if num   2    0    num   3    0    num    int Math sqrt num     0            return false            for int i 4 i lt  int Math sqrt num  i                 if num i  0                return false                   return true

User · Answer

java math BigInteger has a nextProbablePrime   method  Whilst I m guessing this is meant for cryptography you could use it for you work   BigInteger prime   BigInteger valueOf 0   for  int i   0  i  lt  n  i          prime   prime nextProbablePrime      System out println prime intValue

User · Answer

Although many correct and detailed explanations are available  but here is my C implementation    include lt stdio h gt   include lt conio h gt    main     int pk qd am no c 0  printf   n Enter the Number U want to Find    scanf   d   amp no   for pk 2 pk lt  1000 pk      am 0  for qd 2 qd lt  pk 2 qd      if pk qd  0    am 1  break     if am  0  c    if c  no    printf   d  pk   break     getch    return 0

User · Answer

int counter   0   for int i   1    i          if isPrime i          counter         if counter    userInput            print i           break            Edit  Your prime function could use a bit of work  Here s one that I have written   private static boolean isPrime long n        if n  lt  2          return false       for  long i   2  i   i  lt   n  i              if  n   i    0              return false            return true      Note - you only need to go up to sqrt n  when looking at factors  hence the i   i  lt   n

User · Answer

You are trying to do too much in the main method   You need to break this up into more manageable parts   Write a method boolean isPrime int n  that returns true if a number is prime  and false otherwise   Then modify the main method to use isPrime

User · Answer

I just added the missing lines in your own thought process    static int nthPrimeFinder int n             int counter   1     For 1 and 2  assuming n is not 1 or 2          int i   2          int x   2          int tempLength   n           while  counter  lt   n                for    i  lt   tempLength  i                      for  x   2  x  lt  i  x                          if  i   x    0                            break                                                          if  x    i  amp  amp  counter  lt  n                          System out printf   n d is prime   x                       counter                        if  counter    n                            System out printf   n d is prime   x                           return counter                                                                    tempLength   tempLength n                    return 0

User · Answer

I can see that you have received many correct answers and very detailed one  I believe you are not testing it for very large prime numbers  And your only concern is to avoid printing intermediary prime number by your program   A tiny change your program will do the trick      Keep your logic same way and just pull out the print statement outside of loop    Break outer loop after n prime numbers    import java util Scanner         Calculates the nth prime number     author  Zyst      public class Prime       public static void main String   args             Scanner input   new Scanner System in           int n               i   2               x   2           System out printf  This program calculates the nth Prime number n            System out printf  Please enter the nth prime number you want to find             n   input nextInt             for i   2  x   2  n  gt  0  i                  for x   2  x  lt  i  x                      if i   x    0                        break                                              if x    i                    n--                                  System out printf   n d is prime   x

User · Answer

An another solution  import java util Scanner   public class Prime       public static void main String   args            Scanner in   new Scanner System in            int   arr   new int 10000000           for int i 2 i lt 10000000 i                          arr i  i                    for int i 2 i lt 10000000 i                for int j i i j lt 10000000 j  i                  arr j  0           int t   in nextInt            for int a0   0  a0  lt  t  a0                 int n   in nextInt                int count 0              for int j 2 j lt 10000000 j                                  if arr j   0                                        count                        if count  n                                                System out println j                           break                                                                            Hope this will help for larger numbers

User · Answer

public class prime      public static void main String ar                int count        int no 0        for int i 0 i lt 1000 i             count 0          for int j 1 j lt  i j              if i j  0             count                                 if count  2             no              if no  Integer parseInt ar 0                 System out println no   t  i   t

User · Answer

Using Java 8 parallelStream would be faster  Below is my code for finding Nth prime number  public static Integer findNthPrimeNumber Integer nthNumber        List lt Integer gt  primeList   new ArrayList lt  gt         primeList addAll Arrays asList 2  3        Integer initializer   4      while  primeList size    lt  nthNumber            if  isPrime initializer  primeList                 primeList add initializer                     initializer              return primeList get primeList size   - 1      public static Boolean isPrime Integer input  List lt Integer gt  primeList        return   primeList parallelStream   anyMatch i - gt  input   i    0        Test public void findNthPrimeTest         Problem7 inputObj   new Problem7        Integer methodOutput   inputObj findNthPrimeNumber 100       Assert assertEquals  Integer  541  methodOutput       Assert assertEquals  Integer  104743  inputObj findNthPrimeNumber 10001

User · Answer

To calculate the n-th prime  I know two main variants   The straightforward way  That is to count all the primes starting from 2 as you find them until you have reached the desired nth   This can be done with different levels of sophistication and efficiency  and there are two conceptually different ways to do it  The first is  Testing the primality of all numbers in sequence  This would be accomplished by a driver function like  public static int nthPrime int n        int candidate  count      for candidate   2  count   0  count  lt  n    candidate            if  isPrime candidate                   count                         The candidate has been incremented once after the count reached n     return candidate-1      and the interesting part that determines the efficiency is the isPrime function   The obvious way for a primality check  given the definition of a prime as a number greater than 1 that is divisible only by 1 and by itself that we learned in school    is  Trial division  The direct translation of the definition into code is  private static boolean isPrime int n        for int i   2  i  lt  n    i            if  n   i    0                   We are naive  but not stupid  if                the number has a divisor other                than 1 or itself  we return immediately              return false                      return true      but  as you will soon discover if you try it  its simplicity is accompanied by slowness  With that primality test  you can find the 1000th prime  7919  in a few milliseconds  about 20 on my computer   but finding the 10000th prime  104729  takes seconds   2 4s   the 100000th prime 1299709  several minutes  about 5   the millionth prime  15485863  would take about eight and a half hours  the ten-millionth prime  179424673  weeks  and so on  The runtime complexity is worse than quadratic - T n     log n    So we d like to speed the primality test up somewhat  A step that many people take is the realisation that a divisor of n  other than n itself  can be at most n 2  If we use that fact and let the trial division loop only run to n 2 instead of n-1  how does the running time of the algorithm change  For composite numbers  the lower loop limit doesn t change anything  For primes  the number of trial divisions is halved  so overall  the running time should be reduced by a factor somewhat smaller than 2  If you try it out  you will find that the running time is almost exactly halved  so almost all the time is spent verifying the primality of primes despite there being many more composites than primes   Now  that didn t help much if we want to find the one-hundred-millionth prime  so we have to do better  Trying to reduce the loop limit further  let us see for what numbers the upper bound of n 2 is actually needed  If n 2 is a divisor of n  then n 2 is an integer  in other words  n is divisible by 2  But then the loop doesn t go past 2  so it never  except for n   4  reaches n 2  Jolly good  so what s the next largest possible divisor of n  Why  n 3 of course  But n 3 can only be a divisor of n if it is an integer  in other words  if n is divisible by 3  Then the loop will exit at 3  or before  at 2  and never reach n 3  except for n   9   The next largest possible divisor      Hang on a minute  We have 2  lt - gt  n 2 and 3  lt - gt  n 3  The divisors of n come in pairs   If we consider the pair  d  n d  of corresponding divisors of n  either d   n d  i e  d   vn  or one of them  say d  is smaller than the other  But then d d  lt  d  n d    n and d  lt  vn  Each pair of corresponding divisors of n contains  at least  one which does not exceed vn   If n is composite  its smallest nontrivial divisor does not exceed vn   So we can reduce the loop limit to vn  and that reduces the runtime complexity of the algorithm  It should now be T n1 5   v log n    but empirically it seems to scale a little bit better - however  there s not enough data to draw reliable conclusions from empirical results   That finds the millionth prime in about 16 seconds  the ten-millionth in just under nine minutes  and it would find the one-hundred-millionth in about four and a half hours  That s still slow  but a far cry from the ten years or so it would take the naive trial division   Since there are squares of primes and products of two close primes  like 323   17 19  we cannot reduce the limit for the trial division loop below vn  Therefore  while staying with trial division  we must look for other ways to improve the algorithm now   One easily seen thing is that no prime other than 2 is even  so we need only check odd numbers after we have taken care of 2  That doesn t make much of a difference  though  since the even numbers are the cheapest to find composite - and the bulk of time is still spent verifying the primality of primes  However  if we look at the even numbers as candidate divisors  we see that if n is divisible by an even number  n itself must be even  so  excepting 2  it will have been recognised as composite before division by any even number greater than 2 is attempted  So all divisions by even numbers greater than 2 that occur in the algorithm must necessarily leave a nonzero remainder  We can thus omit these divisions and check for divisibility only by 2 and the odd numbers from 3 to vn  This halves  not quite exactly  the number of divisions required to determine a number as prime or composite and therefore the running time  That s a good start  but can we do better   Another large family of numbers is the multiples of 3  Every third division we perform is by a multiple of 3  but if n is divisible by one of them  it is also divisible by 3  and hence no division by 9  15  21      that we perform in our algorithm will ever leave a remainder of 0  So  how can we skip these divisions  Well  the numbers divisible by neither 2 nor 3 are precisely the numbers of the form 6 k    1  Starting from 5  since we re only interested in numbers greater than 1   they are 5  7  11  13  17  19       the step from one to the next alternates between 2 and 4  which is easy enough  so we can use  private static boolean isPrime int n        if  n   2    0  return n    2      if  n   3    0  return n    3      int step   4  m    int Math sqrt n    1      for int i   5  i  lt  m  step   6-step  i    step            if  n   i    0                return false                      return true      This gives us another speedup by a factor of  nearly  1 5  so we d need about one and a half hours to the hundred-millionth prime   If we continue this route  the next step is the elimination of multiples of 5  The numbers coprime to 2  3 and 5 are the numbers of the form  30 k   1  30 k   7  30 k   11  30 k   13  30 k   17  30 k   19  30 k   23  30 k   29   so we d need only divide by eight out of every thirty numbers  plus the three smallest primes   The steps from one to the next  starting from 7  cycle through 4  2  4  2  4  6  2  6  That s still easy enough to implement and yields another speedup by a factor of 1 25  minus a bit for more complicated code   Going further  the multiples of 7 would be eliminated  leaving 48 out of every 210 numbers to divide by  then 11  480 2310   13  5760 30030  and so on  Each prime p whose multiples are eliminated yields a speedup of  almost  p  p-1   so the return decreases while the cost  code complexity  space for the lookup table for the steps  increases with each prime   In general  one would stop soonish  after eliminating the multiples of maybe six or seven primes  or even fewer   Here  however  we can follow through to the very end  when the multiples of all primes have been eliminated and only the primes are left as candidate divisors  Since we are finding all primes in order  each prime is found before it is needed as a candidate divisor and can then be stored for future use  This reduces the algorithmic complexity to - if I haven t miscalculated - O n1 5   v log n    At the cost of space usage for storing the primes   With trial division  that is as good as it gets  you have to try and divide by all primes to vn or the first dividing n to determine the primality of n  That finds the hundred-millionth prime in about half an hour here   So how about  Fast primality tests  Primes have other number-theoretic properties than the absence of nontrivial divisors which composite numbers usually don t have  Such properties  if they are fast to check  can form the basis of probabilistic or deterministic primality tests  The archetypical such property is associated with the name of Pierre de Fermat  who  in the early 17th century  found that     If p is a prime  then p is a divisor of  ap-a  for all a    This - Fermat s so-called  little theorem  - is  in the equivalent formulation     Let p be a prime and a not divisible by p  Then p divides ap-1 - 1    the basis of most of the widespread fast primality tests  for example Miller-Rabin  and variants or analogues of that appear in even more  e g  Lucas-Selfridge    So if we want to know if a not too small odd number n is a prime  even and small numbers are efficiently treated by trial division   we can choose any number a    1  which is not a multiple of n  for example 2  and check whether n divides an-1 - 1  Since an-1 becomes huge  that is most efficiently done by checking whether a  n-1    1  mod n   i e  by modular exponentiation  If that congruence doesn t hold  we know that n is composite  If it holds  however  we cannot conclude that n is prime  for example 2 340   1  mod 341   but 341   11   31 is composite  Composite numbers n such that a  n-1    1  mod n  are called Fermat pseudoprimes for the base a   But such occurrences are rare  Given any base a  gt  1  although there are an infinite number of Fermat pseudoprimes to base a  they are much rarer than actual primes  For example  there are only 78 base-2 Fermat pseudoprimes and 76 base-3 Fermat pseudoprimes below 100000  but 9592 primes  So if one chooses an arbitrary odd n  gt  1 and an arbitrary base a  gt  1 and finds a  n-1    1  mod n   there s a good chance that n is actually prime   However  we are in a slightly different situation  we are given n and can only choose a  So  for an odd composite n  for how many a  1  lt  a  lt  n-1 can a  n-1    1  mod n  hold  Unfortunately  there are composite numbers - Carmichael numbers - such that the congruence holds for every a coprime to n  That means that to identify a Carmichael number as composite with the Fermat test  we have to pick a base that is a multiple of one of n s prime divisors - there may not be many such multiples   But we can strengthen the Fermat test so that composites are more reliably detected  If p is an odd prime  write p-1   2 m  Then  if 0  lt  a  lt  p   a  p-1  - 1    a m   1     a m - 1    and p divides exactly one of the two factors  the two factors differ by 2  so their greatest common divisor is either 1 or 2   If m is even  we can split a m - 1 in the same way  Continuing  if p-1   2 s   k with k odd  write  a  p-1  - 1    a  2  s-1  k    1     a  2  s-2  k    1           a k   1     a k - 1    then p divides exactly one of the factors  This gives rise to the strong Fermat test   Let n  gt  2 be an odd number  Write n-1   2 s   k with k odd  Given any a with 1  lt  a  lt  n-1  if   a k   1  mod n  or a   2 j  k    -1  mod n  for any j with 0  lt   j  lt  s   then n is a strong  Fermat  probable prime for base a  A composite strong base a  Fermat  probable prime is called a strong  Fermat  pseudoprime for the base a  Strong Fermat pseudoprimes are even rarer than ordinary Fermat pseudoprimes  below 1000000  there are 78498 primes  245 base-2 Fermat pseudoprimes and only 46 base-2 strong Fermat pseudoprimes  More importantly  for any odd composite n  there are at most  n-9  4 bases 1  lt  a  lt  n-1 for which n is a strong Fermat pseudoprime   So if n is an odd composite  the probability that n passes k strong Fermat tests with randomly chosen bases between 1 and n-1  exclusive bounds  is less than 1 4 k   A strong Fermat test takes O log n  steps  each step involves one or two multiplications of numbers with O log n  bits  so the complexity is O  log n  3  with naive multiplication  for huge n  more sophisticated multiplication algorithms can be worthwhile    The Miller-Rabin test is the k-fold strong Fermat test with randomly chosen bases  It is a probabilistic test  but for small enough bounds  short combinations of bases are known which give a deterministic result   Strong Fermat tests are part of the deterministic APRCL test   It is advisable to precede such tests with trial division by the first few small primes  since divisions are comparatively cheap and that weeds out most composites   For the problem of finding the nth prime  in the range where testing all numbers for primality is feasible  there are known combinations of bases that make the multiple strong Fermat test correct  so that would give a faster - O n  log n 4  - algorithm   For n  lt  2 32  the bases 2  7  and 61 are sufficient to verify primality  Using that  the hundred-millionth prime is found in about six minutes   Eliminating composites by prime divisors  the Sieve of Eratosthenes  Instead of investigating the numbers in sequence and checking whether each is prime from scratch  one can also consider the whole set of relevant numbers as one piece and eliminate the multiples of a given prime in one go  This is known as the Sieve of Eratosthenes   To find the prime numbers not exceeding N   make a list of all numbers from 2 to N for each k from 2 to N  if k is not yet crossed off  it is prime  cross off all multiples of k as composites   The primes are the numbers in the list which aren t crossed off   This algorithm is fundamentally different from trial division  although both directly use the divisibility characterisation of primes  in contrast to the Fermat test and similar tests which use other properties of primes   In trial division  each number n is paired with all primes not exceeding the smaller of vn and the smallest prime divisor of n  Since most composites have a very small prime divisor  detecting composites is cheap here on average  But testing primes is expensive  since there are relatively many primes below vn  Although there are many more composites than primes  the cost of testing primes is so high that it completely dominates the overall running time and renders trial division a relatively slow algorithm  Trial division for all numbers less than N takes O N1 5    log N     steps   In the sieve  each composite n is paired with all of its prime divisors  but only with those  Thus there the primes are the cheap numbers  they are only ever looked at once  while the composites are more expensive  they are crossed off multiple times  One might believe that since a sieve contains many more  expensive  numbers than  cheap  ones  it would overall be a bad algorithm  However  a composite number does not have many distinct prime divisors - the number of distinct prime divisors of n is bounded by log n  but usually it is much smaller  the average of the number of distinct prime divisors of the numbers  lt   n is log log n - so even the  expensive  numbers in the sieve are on average no more  or hardly more  expensive than the  cheap  numbers for trial division   Sieving up to N  for each prime p  there are T N p  multiples to cross off  so the total number of crossings-off is T    N p     T N   log  log N    This yields much faster algorithms for finding the primes up to N than trial division or sequential testing with the faster primality tests   There is  however  a disadvantage to the sieve  it uses O N  memory   But with a segmented sieve  that can be reduced to O vN  without increasing the time complexity    For finding the nth prime  instead of the primes up to N  there is also the problem that it is not known beforehand how far the sieve should reach   The latter can be solved using the prime number theorem  The PNT says  p x    x log x  equivalently  lim p x  log x x   1     where p x  is the number of primes not exceeding x  here and below  log must be the natural logarithm  for the algorithmic complexities it is not important which base is chosen for the logarithms   From that  it follows that p n    n log n  where p n  is the nth prime  and there are good upper bounds for p n  known from deeper analysis  in particular  n  log n   log  log n  - 1   lt  p n   lt  n  log n   log  log n    for n  gt   6    So one can use that as the sieving limit  it doesn t exceed the target far   The O N  space requirement can be overcome by using a segmented sieve  One can then record the primes below vN for O vN   log N  memory consumption and use segments of increasing length  O vN  when the sieve is near N    There are some easy improvements on the algorithm as stated above    start crossing off multiples of p only at p    not at 2 p eliminate the even numbers from the sieve eliminate the multiples of further small primes from the sieve   None of these reduce the algorithmic complexity  but they all reduce the constant factors by a significant amount  as with trial division  the elimination of multiples of p yields lesser speedup for larger p while increasing the code complexity more than for smaller p    Using the first two improvements yields     Entry k in the array represents the number 2 k 3  so we have to do    a bit of arithmetic to get the indices right  public static int nthPrime int n        if  n  lt  2  return 2      if  n    2  return 3      int limit  root  count   1      limit    int  n  Math log n    Math log Math log n       3      root    int Math sqrt limit    1      limit    limit-1  2      root   root 2 - 1      boolean   sieve   new boolean limit       for int i   0  i  lt  root    i            if   sieve i                   count              for int j   2 i  i 3  3  p   2 i 3  j  lt  limit  j    p                    sieve j    true                                    int p      for p   root  count  lt  n    p            if   sieve p                   count                      return 2 p 1      which finds the hundred-millionth prime  2038074743  in about 18 seconds  This time can be reduced to about 15 seconds  here  YMMV  by storing the flags packed  one bit per flag  instead of as booleans  since the reduced memory usage gives better cache locality   Packing the flags  eliminating also multiples of 3 and using bit-twiddling for faster faster counting      Count number of set bits in an int public static int popCount int n        n -   n  gt  gt  gt  1   amp  0x55555555      n     n  gt  gt  gt  2   amp  0x33333333     n  amp  0x33333333       n     n  gt  gt  4   amp  0x0F0F0F0F     n  amp  0x0F0F0F0F       return  n   0x01010101   gt  gt  24        Speed up counting by counting the primes per    array slot and not individually  This yields    another factor of about 1 24 or so  public static int nthPrime int n        if  n  lt  2  return 2      if  n    2  return 3      if  n    3  return 5      int limit  root  count   2      limit    int  n  Math log n    Math log Math log n       3      root    int Math sqrt limit       switch limit 6            case 0              limit   2  limit 6  - 1              break          case 5              limit   2  limit 6    1              break          default              limit   2  limit 6             switch root 6            case 0              root   2  root 6  - 1              break          case 5              root   2  root 6    1              break          default              root   2  root 6             int dim    limit 31   gt  gt  5      int   sieve   new int dim       for int i   0  i  lt  root    i            if   sieve i  gt  gt  5   amp   1  lt  lt   i amp 31       0                int start  s1  s2              if   i  amp  1     1                    start   i  3 i 8  4                  s1   4 i 5                  s2   2 i 3                else                   start   i  3 i 10  7                  s1   2 i 3                  s2   4 i 7                            for int j   start  j  lt  limit  j    s2                    sieve j  gt  gt  5     1  lt  lt   j amp 31                   j    s1                  if  j  gt   limit  break                  sieve j  gt  gt  5     1  lt  lt   j amp 31                                     int i      for i   0  count  lt  n    i            count    popCount  sieve i              --i      int mask    sieve i       int p      for p   31  count  gt   n  --p            count -   mask  gt  gt  p   amp  1            return 3  p  i lt  lt 5   7  p amp 1       finds the hundred-millionth prime in about 9 seconds  which is not unbearably long   There are other types of prime sieves  of particular interest is the Sieve of Atkin  which exploits the fact that certain congruence classes of  rational  primes are composites in the ring of algebraic integers of some quadratic extensions of Q  Here is not the place to expand on the mathematical theory  suffice it to say that the Sieve of Atkin has lower algorithmic complexity than the Sieve of Eratosthenes and hence is preferable for large limits  for small limits  a not overly optimised Atkin sieve has higher overhead and thus can be slower than a comparably optimised Eratosthenes sieve   D  J  Bernstein s primegen library  written in C  is well optimised for numbers below 232 and finds the hundred-millionth prime  here  in about 1 1 seconds   The fast way  If we only want to find the nth prime  there is no intrinsic value in also finding all the smaller primes  If we can skip most of them  we can save a lot of time and work  Given a good approximation a n  to the nth prime p n   if we have a fast way to calculate the number of primes p a n   not exceeding a n   we can then sieve a small range above or below a n  to identify the few missing or excess primes between a n  and p n    We have seen an easily computed fairly good approximation to p n  above  we could take  a n    n  log n   log  log n     for example   A good method to compute p x  is the Meissel-Lehmer method  which computes p x  in roughly O x 0 7  time  the exact complexity depends on the implementation  a refinement by Lagarias  Miller  Odlyzko  Del  glise and Rivat lets one compute p x  in O x2 3   log   x  time    Starting with the simple approximation a n   we compute e n    p a n   - n  By the prime number theorem  the density of primes near a n  is about 1 log a n   so we expect p n  to be near b n    a n  - log a n  e n  and we would sieve a range slightly larger than log a n  e n   For greater confidence that p n  is in the sieved range  one can increase the range by a factor of 2  say  which almost certainly will be large enough  If the range seems too large  one can iterate with the better approximation b n  in place of a n   compute p b n   and f n    p  b n   - n  Typically   f n   will be much smaller than  e n    If f n  is approximately -e n   c n     a n    b n     2 will be a better approximation to p n   Only in the very unlikely case that f n  is very close to e n   and not very close to 0   finding a sufficiently good approximation to p n  that the final sieving stage can be done in time comparable to computing p a n   becomes a problem   In general  after one or two improvements to the initial approximation  the range to be sieved is small enough for the sieving stage to have a complexity of O n 0 75  or better   This method finds the hundred-millionth prime in about 40 milliseconds  and the 1012-th prime  29996224275833  in under eight seconds     tl dr  Finding the nth prime can be efficiently done  but the more efficient you want it  the more mathematics is involved     I have Java code for most of the discussed algorithms prepared here  in case somebody wants to play around with them        Aside remark for overinterested souls  The definition of primes used in modern mathematics is different  applicable in much more general situations  If we adapt the school definition to include negative numbers - so a number is prime if it s neither 1 nor -1 and divisible only by 1  -1  itself and its negative - that defines  for integers  what is nowadays called an irreducible element of Z  however  for integers  the definitions of prime and irreducible elements coincide

[java] Calculating and printing the nth prime number

Examples related to java

Examples related to primes