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

# Find prime numbers of BigInteger

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
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
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
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
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