Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: need help doing Eratosthenes sieve

1. ## need help doing Eratosthenes sieve

my friend(who is better than me in codding) and I are working on a university homework, but before I get to the point I want to mention that I'm no expert and a total noob in comparison to you guys. (2-weeks coding journey). he had an operation and can't help me so I'm by my own that's why I'm writing here to get some help.
okay, that being said lets hit to the point. the exercise is to make an Eratosthenes-sieve without any multiplication, division nor for loops. Now the problem is that I've written before the professor tell us not to use those things and now I don't know what to do. changing the for loops to while is no big deal but I have no clue how to get rid of the last multiplication at the end of the code.

so I wrote the code and sent it to my fellow he did some changes that I didn't well understand //I will comment on the changes that he did and I would be really thankful if someone did explain some point for me.
1)so first we need to get rid of the for loops and replace it with while which is no big deal and then get rid of the multiplication at the end of the code which is my main problem.
2)help to understand some points.

```import java.util.Scanner;
public class primesieb {
public static void main(String[] args) {
//so we declare values and used the scanner to make an input.
int input = 0;
Scanner in = new Scanner(System.in);

System.out.println("give an int bigger that 1:  ");
input = in.nextInt();

while (input <= 1)
{
//in case the number is smaller than 1.
System.out.println("the Int must be bigger than 1!.");
System.out.println("write an Int bigger than 1: ");
input = in.nextInt();
}
in.close();
//now first i wrote it without "+1" but my friend changed it to +1
boolean[] x = new boolean[input + 1];
//here I just wanted to add this to set that the position 0 in the string is not a prime number but after thinking I don't see its necessary

x=false;

//he did write this commented for loop to assume that all of them are false but for me, it doesn't make sense, pls explain if it's necessary.
//for (int i = 2; i < x.length; i++) {
//  x[i] = false;}

for (int i = 2; i < x.length; i++) {

while (x[i])
{
i++;
}
// here how can we get rid of the multiplication.
//the next for loop and if my friend did and a better explain would be nice helping me to represent my code better.
for (int j = i; j*i < input; j++)
{
x[i * j] = true;
}
if (! x[i] && i < input)
{
System.out.println("the number" + i + "is prime. ");
}
}
}
}```

NOTE I tried now to use the (int)Math.sqrt(i) and I got an Error
`Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 11 at primesiebselber.main(primesiebselber.java:31)`
I have no idea what is this.
and i did try this
`for (int j = i, z= (int)Math.pow (i,j); z < eingabe; j++) { x[z] = true;}`
but the code is showing nothing after my input!!!  Reply With Quote

2. ## Re: need help doing Eratosthenes sieve

Hey.
I tried the code that you're using. It is rather long and only worked for the numbers 3 and 4 for me.
And you didn't get any results on this :

`for (int j = i, z= (int)Math.pow (i,j); z < eingabe; j++) { x[z] = true;}`

because you are using "eingabe" and not "input". Which is something you used in the main code.

You said that you can handle for loops and change them as you please so i made a code that can
do what you seek. But you need to change the loops and add the while loop (i don't know what
your assignment says but i guess that you aren't allowed to use for loops?), incase someone
types in a number under 1. Also try to understand why things are as they are.

```public class MathFollowUp {
public static void main(String[] args) {
System.out.print("Enter number to get prime number : ");
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int j = 1; j < n; j++) {
if (IsPrime(j)) {
System.out.print(j + " ");
}
}
in.close();
}
public static boolean IsPrime(int n) {
if (n > 2 && n % 2 == 0) {
return false;
}
int top = (int) java.lang.Math.sqrt(n) + 1;
for (int i = 3; i < top; i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
}```

Good luck.  Reply With Quote

3. ## Re: need help doing Eratosthenes sieve

Are you trying to do the original sieve by marking values in a list of numbers or one of the shorter versions. The latter only takes about 11 lines of code so I am not certain what you are doing. Here is the basic algorithm for the latter.

1. Set a list of primes to 2 (the first prime).
2. set candidate to 3
3. see if candidate is divisible by any of the primes. (this is where sqrt can come into play)
4. if so, its not a prime so go to 6
5. if so, add it to the list of primes
6. bump candidate by 1.
7. if candidate < max_candidate, go to 3

Of course, you can't use goto's so you can figure that out.

You might also want to contact your professor and let him know of your partner's operation and see if you can't get an extension. Seems like a special situation.

Regards,
Jim  Reply With Quote 