4 Replies Latest reply: Feb 4, 2013 10:07 AM by mycoffee RSS

    Find prime numbers of BigInteger

    831755
      I want to find all the prime number less then some given big integer number.

      like

      BigInteger n=new BigInteger(jTextField1.getText());
      then all prime number less then n.

      While I tried it was giving error the increment and comparison operator can not be applied to BigInt..

      for (i=1;i<n; n.add(BigInteger.ONE)) // Error : -- and >= can not be applied to java.math.BigInteger
                     {
                          
                          int ctr=0;
                          for(x =i; x>=1; x--) // Error : -- and >= can not be applied to java.math.BigInteger
                          {
                                    if(i%x==0) //Error : % can not be applied to java.math.BigInteger
                                    {
                                         ctr = ctr + 1;
                                    }
                          }
                          if (ctr ==2)
                          {
                               System.out.print(" " + i);
                          }
                
                
                     }

      Any solution to this?
        • 1. Re: Find prime numbers of BigInteger
          TPD-Opitz
          Looks like java does not apply autoboxing in this case. It cannot, because a BigInteger can hold values much larger that int could ever hold.

          Depending on how big your initial value can get it might not be suitable to convert the BigInteger to an int, because you'll lose leading digits. So your only chance may be to use a plain <tt>while</tt> and the methods BigInteger offers.

          bye
          TPD
          • 2. Re: Find prime numbers of BigInteger
            mycoffee
            Also, it looks like your algorithm is not efficient. You try to scan ALL numbers from 1 to n and and scan from i to 1 that is N^2. For big number, it can run forever ...
            To check a number whether prime or not you should check with prime numbers only
            So create a List to hold the prime numbers and add to it every time you find one. Then use the List to check the bigger numbers
            • 3. Re: Find prime numbers of BigInteger
              TPD-Opitz
              mycoffee wrote:
              To check a number whether prime or not you should check with prime numbers only
              So create a List to hold the prime numbers and add to it every time you find one. Then use the List to check the bigger numbers
              Additionally you can stop checking when the next prime devider is bigger that the numbers half (which means that the result of the devision is less than two), eg: when checking <tt>23</tt> you will find the result of <tt>11</tt> beeing <tt>2.09...</tt>. The result of <tt>13</tt> is <tt>1.79...</tt>, so you don't need to check <tt>17</tt>.

              bye
              TT
              • 4. Re: Find prime numbers of BigInteger
                mycoffee
                TPD Opitz-Consulting com wrote:
                mycoffee wrote:
                To check a number whether prime or not you should check with prime numbers only
                So create a List to hold the prime numbers and add to it every time you find one. Then use the List to check the bigger numbers
                Additionally you can stop checking when the next prime devider is bigger that the numbers half (which means that the result of the devision is less than two), eg: when checking <tt>23</tt> you will find the result of <tt>11</tt> beeing <tt>2.09...</tt>. The result of <tt>13</tt> is <tt>1.79...</tt>, so you don't need to check <tt>17</tt>.

                bye
                TT
                Yes, but not a half, it is sqrt of the number. For example, when check number 101, you should check if it divisible to 2, 3, 5, 7 and that is it, since the next prime, 11, 11^2 > 101
                Anyway, this is about Math, not about java and I think the forum is not to solve the homework problem :)