Help finding prime numbers in Java.

Strida · Oct 25, 2005

Assignment is to write a program to find the prime numbers that are less than a number you enter. Here's what I have now:

Code:

public class Lab6Part3 {
    public static void main (String[] args) {
        int x, y, upto;
        boolean prime;
        Scanner kb = new Scanner(System.in);
        
        System.out.print("\nEnter a number to find all prime numbers up to it:  ");
        upto = kb.nextInt();
        
        for (x=2; x<upto; x++) {
            prime=false;
            for (y=2; y<upto; y++) {
                if (x%y!=0)
                    prime=true;
                else
                    prime=false;
            }
            if (prime=true)
                System.out.print(x + " ");
        }
    }
}

Here's my output (when I enter 15 as upto):

Code:

Enter a number to find all prime numbers up to it:  15
2 3 4 5 6 7 8 9 10 11 12 13 14

I know that I can make it more efficient, but I wanted to get it working in an easier-to-understand way first.

klingens · Oct 25, 2005

Code:

 if (prime=true)
                System.out.print(x + " ");

That's not a comparison but an assignment making the statement always true as seen on your output. Change it.

Also your y for loop goes too far, y<upto is not good, you should put a lower value into upto

Third you need to work on your assignments of the variable prime. Hint: first, a numbre is always prime, unless you find one case where it isn't. then it's immediately false and you can stop changing that value, ie. no if/else inside the y for loop

MRD · Oct 25, 2005

I think a superior way of approaching this problem would be to use the sieve of eratosthenes. This is a very old and simple algorithm for finding all the primes up to a given integer x. What you do is simply write down all the numbers from 2 to x. Then you take the first number, 2, and cross out all multiples of 2, leaving 2 itself. Then you take the next number that is not crossed out (3 in this case) and cross out all the multiples of 3, leaving 3 itself. Repeat until you are out of numbers. It's a very efficient way of finding all the primes up to x.

Strida · Oct 26, 2005

I know of the sieve of Eratosthenes and I agree it would work better, but I forgot to mention the assignment specified to do it this way. =(

I changed the prime=true to prime==true and still no go, will work on your other suggestions klingens.

BTW, thanks for the help.

9mmCensor · Oct 26, 2005

Whats the error? Whats the current output?

klingens · Oct 26, 2005

Here's a Java compiler and there's the code. Now go and compile it yourself with the added "=" as described.

Gnufsh · Oct 26, 2005

I think we may be missing some needed files:
dan@langley ~ $ gcj prime.java
prime.java:1: error: Public class `Lab6Part3' must be defined in a file called `Lab6Part3.java'.
public class Lab6Part3 {
^
prime.java:5: error: Type `Scanner' not found in the declaration of the local variable `kb'.
Scanner kb = new Scanner(System.in);
^
2 errors

So we either need the rest to work with it, or we need him to tell us what the error/problem is. On the other hand, I haven't used java in about two years.

Gnufsh · Oct 26, 2005

Okay, so I naked the file wrong. I still get this error:
dan@langley ~ $ /opt/blackdown-jdk-1.4.2.02/bin/javac Lab6Part3.java
Lab6Part3.java:5: cannot resolve symbol
symbol : class Scanner
location: class Lab6Part3
Scanner kb = new Scanner(System.in);
^
Lab6Part3.java:5: cannot resolve symbol
symbol : class Scanner
location: class Lab6Part3
Scanner kb = new Scanner(System.in);
^
2 errors

NetworkGuru · Oct 26, 2005

Code:

public class Lab6Part3 {
    public static void main (String[] args) {
        int x, y, upto;
        boolean prime;
        Scanner kb = new Scanner(System.in);
        
        System.out.print("\nEnter a number to find all prime numbers up to it:  ");
        upto = kb.nextInt();
        
        for (x=2; x<upto; x++) {
            prime=true;
            for(y=2;prime && y<x;y++) {
                if (x%y==0)
                    prime=false;
            }
            if (prime || x==2)
                System.out.print(x + " ");
        }
    }
}

I believe this may work, but I have no way of compiling it for testing.

Edit: Changed while loop to a for loop.

JigPu · Oct 26, 2005

You're missing two very important lines if you want to use the Scanner class:

Code:

import java.util.*;
import java.io.*;

Stick these at the top of the .java file, and you'll be set (this should fix you're errors Gnufsh)

After running your revised version, it appears that it works correctly (the difference between == and = will get you every time

). As for speed-ups...

1) All primes are odd except for 2. One quick way to speed up your program would be to explicity print "2", and then look only for odd primes starting at 3.
for (x=2; x<upto; x++) would turn into for (x=3; x<upto; x+=2) AND if (prime || x==2) would turn into if (prime)

2) The highest number you need to test a candidate for is the square root of X. A static method to find square roots is included in Java's math library, so be sure to add import java.math.*; to the top of your file if you do this!
for(y=2;prime && y<x;y++) would turn into for(y=2;prime && y<=Math.sqrt(x);y++)
Even better, you can compute int sqrtX = (int)Math.sqrt(x); before the loop, and then use y<=sqrtX (square root is slow to find... the less times you have to calculate it, the better!

3) Primes are only divisible by other primes. In the S.O.E., an array or list is generally used to test only primes. Since this is trial division though, you can't do that. However, since all primes are odd (except 2), you can get away by trial dividing by only odd numbers.
for(y=2;prime && y<=sqrtX;y++) would turn into for(y=3;prime && y<=sqrtX;y+=2)
More convolutions can be done to extend this idea (eg, instead of +=2 you can alternate between +=2 and +=3 [though you'd probably have to change your for loop to a while loop])

4) Two primality tests are done every time through the loop. The first one make sure that the last number was prime (by evaluating if "prime" is true), and the second tests to see if the current number is prime (and sets "prime" to false if not). You can remove the first test provided you're willing to make you're code a tad bit less readable (I wouldn't put this optimization into whatever you turn in)
for(y=3;prime && y<=sqrtX;y+=2) would turn into for(y=3;y<=sqrtX;y+=2) AND if (x%y==0) { prime=false; } would turn into if (x%y==0) { prime=false; break; }

What will all these optimzations give you? (up to 200,000)
Before: 60 seconds
After: 2 seconds

Yeah, I know I'm crazy about the optizations (especially that last one). Truth is, I've been working on optimizing the heck out of a trial-division algorithm for a few years now (it's a good way to learn how to tweak every last ounce of performance from something) so I know a number of tricks to make this particular algorithm go fast.

EDIT: Noticed a bug in one of my optimzations.. Should be y<=sqrtX (not just less-than!)

JigPu

khiloa · Oct 26, 2005

I just applied some of these changes to my C++ prime finder and it helped the speed by a lot.

Strida · Oct 27, 2005

Awesome, thanks for all of the help guys I have it working!

Edit: I did impor the java.util.*, just forgot to copy/paste it into my code. It seemed to work alright without the java.io.* though.

NetworkGuru · Oct 28, 2005

Wow, nice optimizations! :clap:

Just one little mistake in your first optimization. If the number entered by the user were 2 or less, then explicitly printing 2 would technically be incorrect. This however is fixed by a simple if(upto>=2) statement before the first for loop and then a matching else with some kind of error message, "No primes found". But that's just me being nit-picky.

JigPu · Oct 28, 2005

Good eye, I forgot about that! Dang boundry conditions!

JigPu

marker · Oct 28, 2005

JigPu said:
Yeah, I know I'm crazy about the optizations (especially that last one)

It's nice so see there are still some people that are concerned with optimizations (for speed and/or size). We are so spoiled by optimizing compilers and fast computers that many forget about these details.

I started out doing data (waveform) capture and analysis (FFTs) on microcontrollers (and single board computers) when 5.77 Mhz was fast. Causes you to think about optimizing everything!

klingens · Oct 29, 2005

It's nice so see there are still some people that are concerned with optimizations (for speed and/or size). We are so spoiled by optimizing compilers and fast computers that many forget about these details.

"Premature optimization is the root of all evil" - Donald Knuth

marker · Oct 29, 2005

klingens said:
"Premature optimization is the root of all evil" - Donald Knuth

I agree with that. My philosophy is generally:

1) Get it working (with some planning for the future).
2) Get it working well (optimized).

Step 2 is often overlooked or forgotten. Of course, without some planning, using solid programming practices in step 1, step 2 is too hard to do.

Captain Newbie · Oct 29, 2005

Since we're quoting famous people in here... "Perfection is achieved not when there is nothing more to add, but when there is nothing more to remove." Antoine d'Saint-Expury.

JigPu...NIIIIIICE.

johan851 · Oct 29, 2005

think a superior way of approaching this problem would be to use the sieve of eratosthenes. This is a very old and simple algorithm for finding all the primes up to a given integer x. What you do is simply write down all the numbers from 2 to x. Then you take the first number, 2, and cross out all multiples of 2, leaving 2 itself. Then you take the next number that is not crossed out (3 in this case) and cross out all the multiples of 3, leaving 3 itself. Repeat until you are out of numbers. It's a very efficient way of finding all the primes up to x.

Just had an assignment to do that using queues. Here's what I did...

Code:

	public void computeTo(int n) {
		if (n < 2)
			throw new IllegalStateException();
		this.myMax = n;

		this.myPrimes = new LinkedQueue<Integer>();
		Queue<Integer> numbers = new LinkedQueue<Integer>();
		for (int i = 2; i <= n; i++)  // sets up queue of numbers
			numbers.enqueue(i);

		int nextPrime;
		do {  // The Sieve
			nextPrime = numbers.dequeue();
			this.myPrimes.enqueue(nextPrime);

			for (int k = numbers.size(); k > 0; k--) {
				int value = numbers.dequeue();
				if (value % nextPrime != 0)
					numbers.enqueue(value);
			}
		} while ((nextPrime * nextPrime) < n);

		while (!numbers.isEmpty()) // sends remaining primes to the Prime queue
			this.myPrimes.enqueue(numbers.dequeue());
	}

What will all these optimzations give you? (up to 200,000)
Before: 60 seconds
After: 2 seconds

Actually, this sieve seems pretty fast...fairly close to the 2-second mark.

JigPu · Oct 29, 2005

Sieves will kick trial-division's butt for sequential lists like this. Run your sieve up to 5 million, and I wouldn't be supprised to see you far ahead of what my optimizations give. Trial division sucks because it is an exponential time algorithm (O(n^0.5)), and so will fall behind a sieve more and more as the list gets longer. No amount of optmization will get rid of the exponential nature, only reduce the other (insignificant over time) parts of an implementation's complexity.

The only place where trial division is useful is for calculating the primality of a single number (sieves must compute all primes before the square root of that number, and so can be a lot slower for just a single number), calculating a small primes fast (since constantly hitting memory is slower than just doing the dividing for small lists), or doing primality tests with very limited memory (since sieves require a list of primes to be saved somewhere).

JigPu

Help finding prime numbers in Java.

Member

Member

Senior Member

Member

Disabled

Member

Senior Member

Senior Member

Member

Inactive Pokémon Moderator

Open Source Senior

Member

Member

Inactive Pokémon Moderator

Member

Member

Member

Senior Django-loving Member

Insatiably Malcontent, Senior Member

Inactive Pokémon Moderator

Similar threads