TheGreatDuck TheGreatDuck - 2 months ago 14
Java Question

My code for determining whether prime number exist between intervals is flawed

I wrote code for determining whether arbitrary conjectures claiming there are prime numbers in an interval have counter-examples.

I put in the arbitrary intervals nn and (n+1)(n+1) which should be correct as it is a famous conjecture.

for (int n = 0; n < 100000; n++)
{
int m = 0;
for (int i = n*n; i <= (n+1)*(n+1); i++)
{
int k = 0;
for (int j = 2; j <= Math.sqrt(i); j++)
{
if ((i % j) == 0)
{
k+=1;
break;
}
}
if (k == 0)
{
m+=1;
break;
}
}
if (m == 0)
{
System.out.println("The conjecture has been disproven for n = " + String.valueOf(n));
}
}


It spat out the "counter examples" n = 46340 and n = 80264.

Are there any problems with this code? When I claimed over on MSE that there were counter-examples, I was told primes do exist. So it's clearly flawed. I'm just not sure if this is an internal issue with Java's implementation of modulo or if my code has a bug.

Answer

I believe your algorithm is correct. However, the data type int in Java is not capable to hold numbers that large. Concretely, the maximal value an integer can have is

 Integer.MAX_VALUE = 2.147.483.647

Interesting enough the choice n = 46340 is exactly the smallest n for which your algorithm breaks that barrier, because

 n*n               = 2.147.395.600 < Integer.MAX_VALUE,
 (n+1)*(n+1)       = 2.147.488.281 > Integer.MAX_VALUE.

As a quick fix, you can use the data type long instead, which can store much greater values up until

Long.MAX_VALUE     = 9.223.372.036.854.775.807

If you want to avoid upper barriers completely, you should take a look at the BigInteger class which is designed for precisely that purpose.

Comments