[Java] prime number generator

[merkerguitars]

Ok so I have an assignment which is the following:

There are 25 primes between 2 and 100, and there are 1229 primes between 2 and 10,000. Write a program for which the user inputs an integer N > 2; the program will then display all prime numbers between 2 and N (inclusive), as well as the number of primes between 2 and N. (Your program must actually do the computation to determine if each number is prime, and keep a count of all primes found.)

The output of the program should specify which numbers are the primes between 2 and N, and which number is the number of primes between 2 and N. (In other words, use descriptive text with the output, and it would be a good idea to output the number of primes in a complete sentence!)

Use standard input and standard output for input and output. Your program must prompt the user for the input N. You may assume that the user will input an integer, but not necessarily an integer greater than 2. (In other words, your program must check that the integer input by the user is greater than 2.)

This is what I have so far, I know the format isn't perfect but hey it kinda works. I just can't figure out make a formula/equation for it to work (I switched proffs so i'm really confused)

 package a1;

/**
 * <p>Title: Assignment 1</p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: UWRF</p>
 * @author Eric Merker
 * @version 1.0
 */

import java.io.*;

public class Assignment1 {
  public Assignment1() {
  }
  // add throws IOException so an error doesn't occur
  public static void main(String[] args) throws IOException {

    String userInput;
    int N;
    BufferedReader br;

    br = new BufferedReader(new InputStreamReader(System.in));
    System.out.print("What number would you like to enter? ");
    userInput = br.readLine();
    N = Integer.parseInt(userInput);

    //System.out.println("Well, my favorite number is " + userNum + "!");
    switch (N) {
      case 1: System.out.println("Not a valid prime number");
break; 
    }
    System.out.println("All the primes up to this number are");
//for (userNum = 0; userNum < 400; userNum++);

  }
}

[MageB420666]

Try some nested for loops, run through each of the numbers between 2 and n, dividing each number from 2 to the current number using % division, have a local variable(in the outer loop) set to 0 increment it every time the remainder is 0, if the interior loop completes and the variable is zero, it's a prime number. I think you can figure out how to display each number.

[Pragma]

To check if a number is prime, you only need to check the numbers between 2 and sqrt(n) - saves some math time. Still, it'll be a hell of a lot of processing for large values of n.

Just a thought, might help some.

[Rangsk]

First of all, N in an Integer, not an int. So you need to extract the value from it before you do anything else.

int n = N.intValue();

You shouldn't be using a switch statement on N to see if it's valid, as it can be 0 or a negative number, which your switch statement will not detect. Use an if statement.

if (n <= 1)
{
  System.out.println("Not a valid prime number");
}

You will want to add code in the if statement depending on what functionality you want. I can think of two possibilities:
1) Just quit the program (return statement)
2) Prompt for a new number. In this case, you'll want to replace the if with a while, and repeat the line that asks for a number.

The real question is - what are you currently learning in your class? Loops? Recursion? Arrays?

If that doesn't matter, then the easiest algorithm to understand would be to do the following. I will not give you code for this part, as this is the actual part of the assignment, but this should help you a bit:

Loop from 2 to the user inputted number (n).

Check the value modulus (% in Java) of n with every number between 2 and n-1. The modulus returns the remainder of dividing the two numbers, so if they divide evenly the answer is 0. For example, 10 % 2 = 0, 10 % 3 = 1, 10 % 4 = 2, 10 % 5 = 0, etc

If none of those values were 0, then you should display the value, and increment an ongoing counter of the number of primes. (THINK: How do you make sure that NONE of the values are 0? You'll need something to keep track of this)

Display the final count

Now, here are a couple of notes that might make the algorithm more efficient (these may not be necessary - as I said, I don't know what this program is intending to teach) PLEASE only implement these AFTER getting a working program. It's more important to have a functional program than a fast program.

If you hard-code 2, you can start your loop at 3 and increment by 2, since no even number is prime except for 2.

You really only need to check up to the square root of the max in your modulus loop

You only need to see if the number is divisible by any primes lower than it - if you store the primes in an array, vector, or similar structure, then you can simply check it against the primes you've already found. This also allows you to calculate all the primes first, and then display them however you want, in whatever order you want.

Those are all the simple algorithm improvements I can think of right now. You may be able to think of more.

Hope this helps.

[merkerguitars]

this is what I have so far.......but i do get an error "'else' without 'if' at line 41 (41:9)"

 package a1;

/**
 * <p>Title: Assignment 1</p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: UWRF</p>
 * @author Eric Merker
 * @version 1.0
 */

import java.io.*;

public class Assignment1 {
  public Assignment1() {
  }
  // add throws IOException so an error doesn't occur
  public static void main(String[] args) throws IOException {

    String userInput;
    int N;
    int factor;
    BufferedReader br;

    br = new BufferedReader(new InputStreamReader(System.in));
    System.out.print("What number would you like to enter? ");
    userInput = br.readLine();
    N = Integer.parseInt(userInput);


boolean noFactorFound;
    for (N=2; N <= upperBound; N=++1);{
      factor = 2;
      noFactorFound = true;

      While(factor <= N / 2 && noFactorFound);
      {
        if (N % factor == 0);
        {
          noFactorFound = false;
        }
        else {
          factor++;

          if (no FactorFound) {
          }
        }
      }
    system.out.println ( factor );
 
  }}}

[Pragma]

You have a semicolon trailing at the end of your if statement.

[Rekna]

Here are some optimizations you should implement.

First always increment your counter by 2 (only check if odd numbers are prime, 2 is the only even prime number).

Second save a list of the primes you find and instead of checking if a number is prime by dividing by all numbers between 2 and N only try dividing other primes into it. There is no reason to try and divide non prime numbers into it, as they will already be checked via other primes.

[strcrssd]

The easiest way to find primes (and one we use for our students) is the Eratosthenes Seive.

Information on it can be found here:
http://ccins.camosun.bc.ca/~jbritton/jberatosthenes.htm

A tip: use a binary array to store the numbers. The index of the array is the number you want to identify as prime/non-prime, and the binary value of array[index] is whether or not the index is prime.

[lanar]

Here's some of the perl one I did to knock the rust off... I got a java version as well both implment the Eratosthenes Seive and stops at the sqrt... it works pretty darn quick...
<code>
#!/usr/bin/perl -w
my @prime_list = ();
my @sieve_list = ();
my $end = $ARGV[0];
my $stopping_point = sqrt ($end);
my $debug = 0;
if ($end < 2)
{
*print "Must enter a integer > 1";
*exit 1;
}
print "Finding all primes from 2 to $end \n";
print "\tand stopping the sieve at $stopping_point\n";
# build inital sieve list
for (my $i = 2; $i<=$end; $i++)
{
*push (@sieve_list,$i);
}

*

# ok now we should have the list built up we will loop
# let's prime the pump
my $prime = $sieve_list[0];
my $iterations = 0;
while ( $prime <= $stopping_point )
{
*$iterations += 1;
*# add the prime to the prime list
*push (@prime_list,$prime);
*# strike off the stuff that's not
*my @temp_sieve = ();
*foreach my $test (@sieve_list)
*{
**if ($test == $sieve_list[0])
**{
***next;
**}
**
**# if the number is devisible by the prime, drop it
**$mod = $test % $prime;
**if ($mod)
**{
***push (@temp_sieve,$test);
**}
*}
*@sieve_list = @temp_sieve;
*# get the next prime
*$prime = $sieve_list[0];
}
# add the rest
foreach $prime (@sieve_list)
{
*push (@prime_list,$prime);
}
print "Primes: \n\t";
my $lines = 0;
foreach $prime (@prime_list)
{
*print "$prime";
*if ($lines == 10)
*{
**print "\n\t";
**$lines = 0;
*}
*else
*{
**print "\t";
**$lines += 1;
*}
}
#print "\n";
#print "# of iterations is $iterations \n";
</code>

I will post the java one when I get a chance... they are both not that pretty but they are darned fast..

[FloydianOne]

Here is my C code, you can probably get a good idea on how to implement it in java.... I used Sieve algorithm.

#include <stdio.h>
    
    /* 
     * This allows us to change the number of primes to search
     * without modifying any code
     * For the l337:
     *   use #define to define TRUE and FALSE
     */
    #define MAX 3000

    int main() {
        int i,j;
        char primes[MAX];
        
        /* Set every number as being a prime, for ease of programming */
        for (i = 0; i < MAX; i++) {
            primes[i] = 0; /* 0 = False remember? */
        }
        
        /* 
         * Traverse the array, starting from 2, since 0 and 1 
         * are non-prime
         */
         
         for(i = 2; i < MAX; i++) {
	     primes[i] = 1;
	     
	     for(j = 2; j < i; j++) {
	     	if((i%j) == 0){
		    primes[i] = 0;
                                    }
        }
}
        /*
         * Print out the list of primes
         */
        /* the \n causes a newline to be printed */
        printf("The list of prime numbers from 1 to 3000 is as follows:\n");
        
        /* Traverse array and print out each number, followed by a
         * newline.
         * Accomplish this using printf("%d\n",i);
         * The %d tells printf that there is going to be a decimal
         * number after the comma.
         *
         * Remember that if primes[i] == TRUE, you must print out i
         * since i corresponds to the prime number, primes[i] defines
         * whether its a prime or not.
         */
        
        for(i = 1; i < MAX; i++){
		
		if(primes[i] == 1){
			printf("%d\n",i);
        	}
	}

        return 0;
        
    }