1 2 Previous Next 26 Replies Latest reply: Apr 30, 2008 2:12 AM by 807591 RSS

    Prime Number Program

    807591
      I am trying to construct a program that lists out all the prime numbers between 1 and 100 but I am having an extremely difficult time with it, here is what i want to be printed out:

      PRIMES BETWEEN 1 AND 100

      2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

      this is all I have right now...I've tweaked with it a lot and I havent been able to come up with anything successful so here's the basic outline in original form

      I'm fairly new to java so if for loops and while loops were used it would make more sense to me....I am also familiar with modulo, which I think would be a good tool for this program, right?

      any help you guys give me is really appreciated

      thanks
      public static void main(String args[]) throws IOException
           {
                System.out.println("Prime Numbers from 1 to 100");
                BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); 
                System.out.print("Enter the primes upper bound  ===>>  ");
                final int MAX = Integer.parseInt(input.readLine());
                boolean primes[] = new boolean[MAX];
                computePrimes(primes);
                displayPrimes(primes);
           }
        • 1. Re: Prime Number Program
          807591
          That program looks like you want to use a sieve algorithm (because of the boolean array).
          What about that upper bound? Is the user supposed to input an upper bound between 1 and 100?
          Anyway you didn't say what your problem is.
          • 2. Re: Prime Number Program
            807591
            Make a list of numbers from two to your maximum. A resizeable list would probably be the easiest to work with. Start looping through your list. For each number you come across, remove all the numbers greater than your number which are divisible by that number. In the end, you will have a list of primes.

            ~Cheers
            • 3. Re: Prime Number Program
              807591
              I smell homework.

              J
              • 4. Re: Prime Number Program
                807591
                I don't see what's so difficult about it. You just need to change a few lines.
                import java.io.*;
                
                public class Prime {
                    public static void main(String args[]) throws IOException
                     {
                          System.out.println("Prime Numbers from 1 to 100");
                          BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); 
                          System.out.print("Enter the primes upper bound  ===>>  ");
                          final int MAX = Integer.parseInt(input.readLine());
                          int[] primes={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
                                      59, 61, 67, 71, 73, 79, 83, 89, 97};
                          for(int i=0; primes<=MAX; i++)
                          System.out.println(primes[i]);
                     }
                }
                • 5. Re: Prime Number Program
                  807591
                  You forgot the spaces. And Poland.
                  His output format clearly needs those...
                  //change
                  System.out.println(primes);
                  //to
                  System.out.print(primes[i] + " ");

                  ~Cheers
                  • 6. Re: Prime Number Program
                    807591
                    what i actually want it to do is to let the user input an upper bound and have the program list the prime numbers up to that point. sorry for not being clear enough

                    thanks again
                    • 7. Re: Prime Number Program
                      3004
                      Did you even try the last code that was posted?!?
                      • 8. Re: Prime Number Program
                        807591
                        Did you even try the last code that was posted?!?
                        Did you even read it?


                        OP: I gave you a method that works. Did you try to implement it? What does your program look like so far, and where is it not working?

                        ~Cheers
                        • 9. Re: Prime Number Program
                          807591
                          Or use some initiative and do a search. The prime number algorithm is one of the basic problems that begginners are set. There would be plenty of examples all over the net. Including a recent topic in these fora.
                          • 10. Re: Prime Number Program
                            807591
                            it was probably a mistake for me to say prime numbers between 1 and 100 because what if the user wants to input 1000? i want to have a mathematical function that determines the prime numbers instead of having them listed out

                            i am trying to use the sieve of erosthenes but it is giving me troubles

                            im trying my best to be as clear as possible because english is not my first language, please bare with me
                            • 11. Re: Prime Number Program
                              807591
                              do you think you could write a routine
                                boolean prime(int x){
                                // this routine should return true if x is prime
                                // your code goes here ...
                                }
                              What are the divisors of a prime number?
                              What is the relationship between modulo and divisors?
                              How can you use modulo to test if a number divides x?
                              How many numbers do you need to check if they are divisors of x before you decide x is prime?
                              If you could write a function that detects prime numbers, how you could you put that into a for loop to print out only the numbers that pass the prime function?

                              Which of those questions is the hard one?
                              • 12. Re: Prime Number Program
                                807591
                                i am trying to use the sieve of erosthenes but it is
                                giving me troubles
                                Do you need to use this algoritm? Can't you just use the definition of a prime number; that it's not evenly divisible by anything else but 1 and itself,
                                boolean isPrime(int N) {
                                   for (int i=2; i<N; i++) // all i from 2 to N-1
                                      if ((N%i) == 0) // N is evenly divisible by i ?
                                         return false; // yes - no prime
                                   return true; // prime
                                }
                                • 13. Re: Prime Number Program
                                  807591
                                  You can test 2 as a separate case, then start i = 3 and increment by 2.
                                  Also, you can put the stop case to i <= Math.sqrt(N).
                                  • 14. Re: Prime Number Program
                                    807591
                                    Here is a program that uses the sieve of Eratosthenes to find all prime numbers between 1 and 1billion. Thats about 50million prime numbers which are all stored into an array. The program needs only a few seconds on a modern PC. You can also change the program to print them out but that might take a little bit longer.
                                    public class Prime {
                                    
                                    final static int N=50847534;
                                    final static int BUFFER=10000;
                                    
                                    public static void main(String[] argv) {
                                        int[] prim, primi;
                                        int pos, pos_prime, i, prime, prime_sqr;
                                        long time_start, time_ges;
                                        int[] buffer=new int[BUFFER];
                                        int start, end;
                                        
                                        prim=new int[N];
                                        primi=new int[10000];
                                        time_start=System.currentTimeMillis();
                                        
                                        for(i=0; i<BUFFER; i++) buffer=1;

                                    buffer[0]=0;
                                    prim[0]=2;

                                    pos_prime=0;
                                    pos=0;
                                    start=0;
                                    end=BUFFER*2-1;

                                    for(; ;) {
                                    while(buffer[++pos]==0);
                                    prime=pos*2+1;
                                    prim[++pos_prime]=prime;
                                    i=(prime*prime)/2;
                                    if(i>=BUFFER) break;
                                    for(; i<BUFFER; i+=prime)
                                    buffer[i]=0;
                                    primi[pos_prime]=i-BUFFER;
                                    }
                                    for(pos++; pos<BUFFER; pos++) {
                                    if(buffer[pos]==1) {
                                    prim[++pos_prime]=pos*2+1;
                                    }
                                    }


                                    do {

                                    pos=0; start+=BUFFER*2; end+=BUFFER*2;
                                    for(i=0; i<BUFFER; i++) buffer[i]=1;

                                    for(pos=1, prime=prim[pos], prime_sqr=prime*prime; prime_sqr<=end; prime=prim[++pos], prime_sqr=prime*prime) {


                                    if(prime_sqr < start )
                                    i=primi[pos];
                                    else
                                    i=(prime_sqr/2)%BUFFER;

                                    for(; i<BUFFER; i+=prime)
                                    buffer[i]=0;

                                    primi[pos]=i-BUFFER;
                                    }

                                    for(pos=0; pos<BUFFER; pos++) {
                                    if(buffer[pos]==1) {
                                    prim[++pos_prime]=start+pos*2+1;
                                    if(pos_prime>=(N-1)) break;
                                    }
                                    }



                                    } while(pos_prime<(N-1));


                                    time_ges=System.currentTimeMillis()-time_start;
                                    System.out.println("Total number of primes found: "+(pos_prime+1));
                                    System.out.println("Largest prime found: "+prim[pos_prime]);
                                    System.out.println("Time: "+((double)time_ges/1000)+" seconds");
                                    }

                                    }
                                    1 2 Previous Next