# Thread: generating prime numbers...using an array

1. Member
Join Date
Feb 2011
Posts
2
Rep Power
0

## 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;
}
}
}

}

2. Member
Join Date
Feb 2011
Posts
18
Rep Power
0
I dont know if its just me but i found your code quite confusing.
here is how i would do it:
Java 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

3. Member
Join Date
Feb 2011
Posts
2
Rep Power
0
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

4. Member
Join Date
Feb 2011
Posts
18
Rep Power
0
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.
Last edited by mr_guy; 03-01-2011 at 05:23 AM. Reason: Edit becuse of sunde887's post below

5. 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
Java 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
Java Code:
```num[0] == 0
num[1] == 1
num[2] == 2
...
num[10] == 9```
Last edited by sunde887; 03-01-2011 at 05:21 AM.

6. This is performing the Sieve of Eratosthenes and I find it much easier to use an array of booleans.

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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•