Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

prime numbers...

Posted on 2011-10-28
15
Medium Priority
?
453 Views
Last Modified: 2012-05-12
To detect prime numbers up to 6, the following print out shows only 5 using the attached code:

  no. %  div. ==  0   prime
----------------------------
C 2
C 3
A 4   %   2   ==  0    
A 5   %   2   ==  1    5
C 5

Please ignore letters A and C at the beginning of the lines.
 
Question: How can I change this code to show:

  no. %  div. ==  0   prime
----------------------------
C 2                            2
C 3                           3
A 4   %   2   ==  0    
A 5   %   2   ==  1    5
C 5

with columns %, no. and div. to be populated as required.

Thank you
public class PrimeTest { 
    public static void main(String[] args) {

       int number =2;
       int numberOfPrimes=6;
       
        // Repeatedly find prime numbers
       System.out.println("  no. %  div. ==  0   prime");
       System.out.println("----------------------------");
        while( number < numberOfPrimes) {  
          if(isPrime(number)){
                System.out.println("C "+number);
          }
          number++;
        }
    }

    public static boolean isPrime(int number) {

        for (int divisor = 2; divisor <= number/2; divisor++) {

            System.out.println("A "+number+"   %   "+divisor +"   ==  "
                + (number % divisor)+"    "+((number % divisor==0)? "":number));

            if (number % divisor ==0) {
                return false;
            };
        }
    return true;
    }
}

Open in new window

0
Comment
Question by:Mike Eghtebas
  • 5
  • 5
  • 3
  • +1
15 Comments
 
LVL 28

Expert Comment

by:dpearson
ID: 37050998
Sounds like a homework problem?  In general we don't do those.  Is there a specific question you have about this?
0
 
LVL 41

Assisted Solution

by:HonorGod
HonorGod earned 200 total points
ID: 37051039
One problem is that you have the System.out.println() within the for loop.

Let's "play computer", for a value of "number" == 2

The loop within isPrime() looks like:

  for ( int divisor = 2; divisor <= 2 / 2; divisor++ ) {
    if ( number % divisor == 0 ) {
      return false;
    }
  }
  return true;

That looks reasonable.
So, the whole program looks like this...

and the output looks like that...

I'll let you play with the output to get it to look like you want...

public class primes { 
    public static void main(String[] args) {

       int number =2;
       int numberOfPrimes=6;
       
       System.out.println("  no. %  div. ==  0   prime");
       System.out.println("----------------------------");
        while( number < numberOfPrimes) {  
          if(isPrime(number)){
                System.out.println( number );
          }
          number++;
        }
    }

    public static boolean isPrime(int number) {
        for (int divisor = 2; divisor <= number/2; divisor++) {
            if (number % divisor ==0) {
                return false;
            };
        }
    return true;
    }
}

Open in new window

no. %  div. ==  0   prime
----------------------------
2
3
5

Open in new window

0
 
LVL 47

Expert Comment

by:for_yan
ID: 37051280
If your goal is to determine first n (say 6 in this case) prime numbers,
frst I'd modfy your method isPrime() becuuse 2 and 3 are specifial, so you may treat them spaarately,
other than that your method wroks fine (I  also suggest to comment out a little misleading printout):

   public static boolean isPrime(int number) {
        if(number == 2 || number == 3)return true;

        for (int divisor = 2; divisor <= number/2; divisor++) {

           // System.out.println("A "+number+"   %   "+divisor +"   ==  "
            //    + (number % divisor)+"    "+((number % divisor==0)? "":number));

            if (number % divisor ==0) {
                return false;
            };
        }
    return true;
    }

Open in new window


and then in the main method I'd create ArrauyList

ArrayList<Integer>  ar= new ArrayList<Integer>();
and then start with num = 2
and then make a

while(true) {


}
loop and insaide this loo I'll chek each numbe with your method isPrime()
if it is true I'll add the number to arraylist, check if I have enough numbers in arraylist
and break if it is enough,
otherwise increement my running num value
and go back into the while loop
ad check the new number;
after I broke outside of the loop
I'd print the  arraylist


So these are obviously the first 6 numbers which I found this way:

[2, 3, 5, 7, 11, 13]

Open in new window


I know you are not in any class;
Please confirm it and I'll post the whole code




0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 34

Author Comment

by:Mike Eghtebas
ID: 37051816
re:> Sounds like a homework problem?

I guess you meant to write: Sounds like a homework problem.

Taking it as question, yes it sounds like a homework question but it isn't. You will see many questions like this from me because I am self studying using a text book. I love java.

================
HonorGod & for_yan,

Thanks for the inputs. This post is one of my worst questions. Basically, this is a very simple routine to code but I had a mental block dealing with line 20 in the original post:

for (int divisor = 2; divisor <= number/2; divisor++) {

wondering why number/2?

I changed it to

for (int divisor = 2; divisor <= number-1; divisor++) {

which works and gives me correct results although it may a bit less efficient ( in processing numbers in hundreds).

I will go through your comments shortly.

Mike

0
 
LVL 47

Assisted Solution

by:for_yan
for_yan earned 200 total points
ID: 37051821
Actually this was not a mental block - but a rather smart move - why to test
those which are bigger than number/2 - they cannot be divisors of a number.
You just need to be a little bit more careful with the bginning of the list - just check
2 and 3 as special case. Other than that checcking only those less than number/2 - this is quite a smart
thing - and will be more efficient
0
 
LVL 47

Expert Comment

by:for_yan
ID: 37051829

This is my full code, corresponding to above description
(maybe I was wrong to abandon your format; left C in th ebeginning if the line - don't know waht that means)

Also made 10 first primes - a ltlle bit more interesting:

import java.util.ArrayList;

public class PrimeTest {
    public static void main(String[] args) {

       int number =2;
       int numberOfPrimes=10;

        ArrayList<Integer> ar = new ArrayList<Integer>();

        int numb  = 2;
        while(true){
            if(isPrime(numb)){
                ar.add(numb); if(ar.size() == numberOfPrimes)break;
            }
            numb++ ;


        }
        
      //  System.out.println(ar);

        for(Integer ii : ar){

            System.out.println("C " + ii );
        }


        // Repeatedly find prime numbers
   //    System.out.println("  no. %  div. ==  0   prime");
     //  System.out.println("----------------------------");
        while( number < numberOfPrimes) {
          if(isPrime(number)){
       //         System.out.println("C "+number);
          }
          number++;
        }
    }

    public static boolean isPrime(int number) {
        if(number == 2 || number == 3)return true;

        for (int divisor = 2; divisor <= number/2; divisor++) {

           // System.out.println("A "+number+"   %   "+divisor +"   ==  "
            //    + (number % divisor)+"    "+((number % divisor==0)? "":number));

            if (number % divisor ==0) {
                return false;
            };
        }
    return true;
    }


    
}

Open in new window



C 2
C 3
C 5
C 7
C 11
C 13
C 17
C 19
C 23
C 29

Open in new window

0
 
LVL 28

Accepted Solution

by:
dpearson earned 1600 total points
ID: 37051834
The "?" for homework was because it's not clear if this is homework or not :)

I think you have the correct algorithm here - the "isPrime()" logic is correct (for n > 2).  It's just the println() that needs to be moved out of the isPrime() method look and into the main function.

FYI, if you want to make it as efficient as possible the limit to use in the loop is actually Math.sqrt(n) as that's the biggest factor that a number can have:

for (int divisor = 2 ; divisor <= Math.sqrt(number) ; divisor++) {
    // Number has a factor
    if (divisor % number == 0)
       return false ;
}

return true ;

If you do that you also don't need to special cases for 2 and 3.

Doug
0
 
LVL 34

Author Comment

by:Mike Eghtebas
ID: 37051900
I had letters like A, B, C to easily locate the locations of System.out... lines in the code.

for_yan,
Your comment: "why to test those which are bigger than number/2 - they cannot be divisors of a number." made it so easy to see why number/2 was used.

dpearson,
re:> I think you have the correct algorithm here.

You the code was good; I was just trying to understand the reason behind the use of number/2. Also thanks for the info on Math.sqrt(n).

Apparently, producing prime numbers for numbers in the range of 10EXX where XX is 2 or more digits is highly in demand the outputs of such numbers could be sold in millions. And, a routine to produce these kind of results may take at least a year of continues-run.

I suppose for higher-range numbers like these the use of Math.sqrt(n) or better method is a must.

Using multi-threading techniques in addition to the use of Math.sqrt(n), I wonder if one could retire sooner by producing a much larger list of prime numbers? LOL it may be possible.

Mike
0
 
LVL 34

Author Comment

by:Mike Eghtebas
ID: 37051901
correction...

Yes the code was good; I ...
0
 
LVL 47

Expert Comment

by:for_yan
ID: 37051904
Oh, this is a very big deal - and the methods they use for seraching for big numbers are far more complicated.
If you wish, you can even participate in the serach for big prime numbers (allocatee you r computer time to it and even get reward
if you hit the new prime - though probablitily to win lottery is probably higher);
Lokk here for that:
http://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search

This however goes far beyond any java exercise.

0
 
LVL 47

Expert Comment

by:for_yan
ID: 37051951
If you are interested in java exercises with  primes,
this is a nice program which implements Eratosthenes
sieve to find all primes less than some number from this site:
http://www.raditha.com/java/primes.php

import java.util.Arrays;

public class Eratosthenes
{
    int max;
    int primes[];



    public static void main(String args[])
    {
        Eratosthenes erat = new Eratosthenes(100);
        erat.find_primes();
        System.out.println(Arrays.toString(erat.primes));
    }
    public Eratosthenes(int max)
    {
        this.max = max;
    }

    public void find_primes()
    {
        int i,j,k, divisor, offset;

        double sqrt = Math.sqrt(max)+1;
        int tmp[];

        if(max  > 100)
        {
            primes = new int[max/2];
        }
        else
        {
            primes = new int[max];
        }
        primes[0] = 2;
        primes[1] = 3;

        for(i=2,j=5; j < max ; j+=2)
        {
            if(j % 3 != 0)
            {
                primes[i++] = j;
            }
        }

        for(i=2, divisor=5, offset = primes.length; divisor < sqrt ; )
        {
            j = i*i;
            tmp = new int[offset];
            offset = j;

            /*
             * Copy the numbers that have already been sieved to a new array.
             */
            System.arraycopy(primes,0,tmp,0,j);
            while( j < tmp.length)
            {
                k = primes[j++];
                if(k==0)
                {
                    /*
                     * The array may contain some zeros at the end. It's too much
                     * trouble to calculate the exact size for the array. Easier
                     * to pad with zeros
                     */
                    break;
                }
                if(k % divisor != 0)
                {
                    tmp[offset++] = k;
                }
            }
            primes = null;
            primes = tmp;
            tmp = null;
            divisor = primes[i++];
        }
    }
}

Open in new window


Output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 0, 0]

Open in new window

0
 
LVL 28

Expert Comment

by:dpearson
ID: 37053424
Just to clarify why sqrt(n) is sufficient, think for example about testing for the factors of 100.

Any factor that divides into n which is larger than the square root (10 in this example) must go into n less times than the square root.  For example, 20 is a factor of 100 but since it's larger than the square root, it must go into 100 less than 10 times (in this case 5 of course).  So you would have already found this factor when testing the value 5.

That's why it's enough to test up to Math.sqrt(n).  n2/ and n-1 will also work as limits, they'll just be repeating tests.

As for finding really large primes - as you say if you could do that (a) you could make a lot of money and (b) you could break many encryption algorithms in use today :)

Good luck on both!

Doug
0
 
LVL 34

Author Closing Comment

by:Mike Eghtebas
ID: 37053447
Thanks to all. The points distributed are a bit skewed in favor of Doug because it is the end of the month and the experts like to satisfy their quotas. I hope the others wouldn't object to this.

Regards,

Mike

I have another question coming up shortly. I will post a link here.
0
 
LVL 41

Expert Comment

by:HonorGod
ID: 37056084
Thanks for the assist and the points.

Good luck & have a great day.
0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Suggested Courses
Course of the Month20 days, 19 hours left to enroll

810 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question