# generating prime numbers...using an array

• 02-28-2011, 03:34 AM
yingyang69
generating prime numbers...using an array
I am trying to complete a class assignment and am currently unsuccessful...the assignment requires:
This program requires that you find all of the primes between 1 and some number that you allow the user to input.

Fill an array with the consecutive integers between 1 and the top number.
Identify 2 as the first prime and then remove all numbers that are evenly divisible by 2 (use modulus function).
Go to the next number remaining on the list (the next prime); now remove all of the numbers divisible by it.
Continue until you have only prime numbers in your list. When can you stop?
Now, write a Java program that generates all of the primes between 2 and some upper bound (greater than 50) that you allow the user to enter. As intermediate data, print one line for each divisor you eliminate along with the numbers eliminated. For example:
2: 4 6 8 10 12 14 16 18...
3: 9 15 21 27

so far I have the following code, but it isn't working...

Scanner keyboard = new Scanner(System.in);
int size;
int sentinel = 0;
int [] numberArray;

System.out.println("Enter the size of the array from 1 to 100:");
size = keyboard.nextInt();
numberArray = new int[size];

//Fill the array.
for (int i=0; i<size; i++)
{
numberArray[i]=i+1;
}

//Identify 2 as the first prime number and then remove all numbers that are evenly divisible by 2
int baseNumber = 2;
for (int i=1; i<size; i++)
if (numberArray[i] != sentinel)
{
int base = numberArray[i];
System.out.print(base + ": ");
if (numArray[i]%baseNumber == 0)
{
System.out.print(numberArray[i] + " ,");
numberArray[i] = sentinel;
}
}
}

}
• 02-28-2011, 06:02 AM
mr_guy
I dont know if its just me but i found your code quite confusing.
here is how i would do it:
Code:

```Scanner keyboard = new Scanner(System.in);         int size;                int [] numberArray;         int [] out;         System.out.println("Enter the size of the array from 1 to 100:");         size = keyboard.nextInt();         numberArray = new int[size];         //Fill the array.         for (int i=1; i<size; i++)         {         numberArray[i]=i;         }                 numberArray[1] = -1;         //Identify 2 as the first prime number and then remove all numbers that are evenly divisible by 2       //start the for loop with 2         for (int i=2; i<size; i++){                 //if the number has not already been discluded                 if(numberArray[i] != -1){                         for(int j = 0; j < size; j++ ){                                 // if the number is a multiple of another number                                 if(numberArray[j]%numberArray[i] == 0 && numberArray[j] != numberArray[i] ){                                         //disclude it                                         numberArray[j] = -1;                                 }                         }                 }                }         //disclude 2         numberArray[2] = -1;                 //print         for(int i = 1; i < size; i ++){                 if(numberArray[i] != -1)                         System.out.print(numberArray[i] + ", ");         }```
ps. please use code tags around your code
• 02-28-2011, 04:47 PM
yingyang69
thank you very much! how do i get the code to output the excluded numbers as well...we are supposed to output the number: its excluded multiples
ex:
2: 4 6 8 10 etc
• 02-28-2011, 05:21 PM
KevinWorkman
• 03-01-2011, 05:04 AM
mr_guy
you can change the code to make it more similar to yours and make it print as you go or you can edit the printing part on the pecie of code i made so it prints the multiples.
its just a simple matter of inserting another 'for' loop and multiplying the number by the increasing variable.
• 03-01-2011, 05:14 AM
sunde887
Please don't spoon feed. What does he learn from you providing the source code? Give him pseudocode or push him in the right direction, this way he will learn to solve problems more efficiently, with less help from others.

Also, the fill the array code will leave the first spot in the array null
it should be
Code:

```for(int i = 1; i <= size; i++ //or for(int i = 0; i < size; i++){   numArray[i - 1] = i; }```
Your method would produce something like
Code:

```num[0] == 0 num[1] == 1 num[2] == 2 ... num[10] == 9```
• 03-01-2011, 05:58 AM
Junky
This is performing the Sieve of Eratosthenes and I find it much easier to use an array of booleans.
• 03-01-2011, 06:30 AM
sunde887
By the way Mr_guy, I am not trying to be rude, but think about it, if you come here with a problem and someone just posts you the code you are a lot less likely to understand how something works.