TheGreatDuck - 6 months ago 38

Java Question

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 n*n 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.