This discussion is archived
4 Replies Latest reply: Feb 4, 2013 8:07 AM by 800411 RSS

Find prime numbers of BigInteger

831755 Newbie
Currently Being Moderated
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-Consulting-com Expert
    Currently Being Moderated
    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
    800411 Newbie
    Currently Being Moderated
    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-Consulting-com Expert
    Currently Being Moderated
    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
    800411 Newbie
    Currently Being Moderated
    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 :)

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points