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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: need help doing Eratosthenes sieve

  1. #1
    Junior Member
    Join Date
    Apr 2019
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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[0]=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!!!
    Last edited by kjzlres; April 21st, 2019 at 08:59 AM.

  2. #2
    Member MrLowBot's Avatar
    Join Date
    Nov 2018
    Location
    Sweden
    Posts
    130
    Thanks
    0
    Thanked 2 Times in 2 Posts

    Default 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.
    "Tick, tack"

  3. #3
    Member
    Join Date
    Sep 2018
    Location
    Virginia
    Posts
    284
    My Mood
    Cool
    Thanks
    0
    Thanked 38 Times in 36 Posts

    Default 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

Similar Threads

  1. need help java multiplication table
    By darking123 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: October 2nd, 2012, 08:49 AM
  2. Sieve of Eratosthenes: Memory & Performance
    By bgroenks96 in forum Algorithms & Recursion
    Replies: 13
    Last Post: June 29th, 2012, 06:41 AM
  3. Multiplication program
    By PhilThomspon in forum What's Wrong With My Code?
    Replies: 2
    Last Post: May 6th, 2012, 01:54 PM
  4. Multiplication code
    By bomboy in forum What's Wrong With My Code?
    Replies: 4
    Last Post: January 5th, 2011, 02:25 AM
  5. sieve of eratosthenes
    By rsala004 in forum Collections and Generics
    Replies: 5
    Last Post: December 29th, 2010, 10:37 AM

Tags for this Thread