r/javahelp • u/aqunox • Mar 12 '15
Prime Calculator Program (Help!)
This program is supposed to calculate a prime number, add it to the prime list, and use it again to find more primes by the remainder. For some reason it doesn't calculate the right number of primes and shows numbers that are not prime. I sort of did trial and error but I keep failing. Please Help!
import java.util.Scanner;
public class PrimeCalc{
public static void main(String[] args) {
/*
* This program finds a number of primes defined by the user in order.
* uses primes added to the list to calculate new primes
*/
Scanner input = new Scanner(System.in);
System.out.println("Enter the number of prime numbers you want to find");
int numOfPrimes = input.nextInt();
int[] primes = new int[numOfPrimes];
int[] primeslist = new int[numOfPrimes];
int count = 0;
int temp = 2;
System.out.println("The list of primes:");
System.out.println("2");
for (int k = 0; k < numOfPrimes; k++){
primeslist[k] = 2;
for (int j = 0; j <= k; j++){
if (temp % primeslist[j] != 0){
primes[k] = temp;
System.out.println(primes[k]);
count++;
j = k+1;
}
}
temp++;
}
}
}2
u/somnolent Mar 12 '15
Well, you're getting bad primes because you aren't requiring that the potential prime isn't divisible by all prior primes, you're only requiring that it isn't divisible by one of them. In your case, you end up with a bunch of odd numbers in your primes list because they aren't divisible by your first prime (2) and you treat them as a prime.
The reason you're getting weird counts back is that you're looping from k to numOfPrimes, but what happens if k isn't a prime? You never get a chance to fill in that spot of the array again. You need to separately track your potential prime vs your array location.
1
u/viciu88 Intermediate Brewer Mar 12 '15
fixed your checking is temp is prime
boolean isPrime = true; //assuming temp is a prime
for (int j = 0; j <= k && isPrime; j++) //for each already found prime
if (temp % primeslist[j] == 0) //if primelist[j] is divisor of temp
isPrime = false; //then its not a prime
if(isPrime)
{//we checked all and it's still a prime
primes[k] = temp;
System.out.println(primes[k]);
count++;
}1
u/DevFactor-Net Mar 12 '15
Your algorithm is just a bit off, everything else looks solid. Check out this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
2
u/autowikibot Mar 12 '15
In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.
The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.
The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes. It is named after Eratosthenes of Cyrene, a Greek mathematician; although none of his works has survived, the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.
====
Interesting: Generating ^primes | Sieve of ^Sundaram | ^Eratosthenes | Sieve ^theory
Parent commenter can toggle ^NSFW or ^delete. Will also delete on comment score of -1 or less. | FAQs | ^Mods | Magic ^Words
1
u/aqunox Mar 12 '15
I would be great if someone could improve this :)