So I was trying to make a prime number calculator in java that goes from 1 up to the upper limit of the range given by the user and prints out all of the primes.
One way of approaching this was by simply using a nested for loop and testing divisibility for every number in the range by all of the numbers less than it.
However, I figured it would be more efficient to only test prime numbers to avoid repeated factors and speed up the program.
For example, if the number we were on was 16, rather than testing if it's divisible by 2,3,4,5,...14,15,16, I could only test out 2,3,5,7,11,13 and stop once a factor is found.
So I tried to make an array to store all of the primes found so far and only use those values to test for the next number.
Here's my code, I can't figure out why it's not working
Scanner sc = new Scanner (System.in);
System.out.print ("Enter the upper limit: ");
int high = sc.nextInt();
boolean isPrime = true;
int[] primearray = new int[0];
for (int num = 1; num <= high; num++)
{
for (int x: primearray)
{
if (num%x==0)
{
isPrime = false;
break;
}
}
if (isPrime == true) {
int size = primearray.length;
primearray = new int[size+1];
primearray [size] = num;
System.out.println (num);
}
}
As you say the key simplification is to only test primes when you find the next prime. For example:
public class PrimeGenerator {
private long current = 1;
private final List<Long> primes = new ArrayList<>();
public long next() {
do {
current++;
} while (primes.stream().anyMatch(n -> current % n == 0));
primes.add(current);
return current;
}
public LongStream stream() {
return LongStream.generate(this::next);
}
}
This records each prime as it is generated.
You can generate get all primes to a certain value with
generator.stream().takeWhile(p -> p < value)...