10 replies to this topic

[Gman]

Hi All

i am doing a few revision practicals and one of them is " Display all the Prime numbers between 1 and 100 " have the code done but was looking for Professional eyes to look over my code and tell me what it is doing. Just explain to me how it is doing what it is doing?

//gman

//10.12.2011





public class PrimeNumQ7

{


		public static void main (String []args)

		{

		

		

		int i =0;

		int x =0;

		String  primeNumber = "";

			

			for (i = 1; i <= 100; i++) 

			{ 

				

				 int ctr=0;

				 for(x =i; x>=1; x--)

				 {

				 		if(i%x==0)

				 		{

							ctr = ctr + 1;

						}

				 }

				 if (ctr ==2)

				 {

				 	primeNumber = primeNumber + i + " ";

				 }

		

		

			}

			

			System.out.print("Prime numbers from 1 - 100 are : \n" + primeNumber);

			

		

		

		}

		

}

Thanks

Gman

[Csabi]

I will try to explain it, sorry for my bad english :D

A prime number is a number that can be divided only by two numbers, the number itself and 1.
When checking a particular number your code divides the given number with each number from 1 to the given number and counts how many times was possible to divide without remainder (remainder = 0)
If the divisions without remainder number was exactly 2 than this means that the number was divided only with 1 and the number itself to have no remainder so it`s a prime number.

Your script loops through each number from 1 to 100 and completes the above steps on each number, and when the script finds a prime number it ads the number to a string and at the end of your code it prints out the result string

[Sinipull]

You need to check if the number divides by any of the previous prime numbers. There's no need to check for every number. Start from the lower primes, because it's much bigger chance that the number divides by 2 or 3 or 5 than for example 23. If it divides by any of the lower prime numbers, you can break out of the loop to minimize cycles.

Also, there's no need to check any primes above the i/2 line. For example 100 can not evenly divide by any number over 50, because it's certain, that the answer is less than 2.

[Csabi]

And you could start the loop from 2 to i/2 and instead of counting the divisions number you could use a boolean value, for example at the beginning you set prime = true and if your number can be divided set it to false

[fread]

If my math is correct you only need to check up to square_root(n) where n is the 100 in this case.

[mebob]

Here's something that may help: Sieve of Eratosthenes - Wikipedia, the free encyclopedia.

[Gman]

Thanks for your first reply it has helped :) i am only at the programming 4 months and we are only at for loop, what did you mean by ....

Csabi said:

And you could start the loop from 2 to i/2 and instead of counting the divisions number you could use a boolean value, for example at the beginning you set prime = true and if your number can be divided set it to false

haven't done anything on boolean as of yet but would mind looking it up or if you had time to show me my code with a boolean value.

Gman

[Csabi]

A boolean is a variable that can only be true or false, is that simple.
Your code would look like this:

public class PrimeNumQ7

{


		public static void main (String []args)

		{

		

		

		int i =0;

		int x =0;

		String  primeNumber = "";

			

			for (i = 1; i <= 100; i++) 

			{ 

				

				 boolean is_prime = true; 


				 for(x =i/2; x>=2; x--)

				 {

				 		if(i%x==0)

				 		{

							is_prime = false;

						}

				 }

				 if (is_prime)  //this is equal with is_prime == true

				 {

				 	primeNumber = primeNumber + i + " ";

				 }

		

		

			}

			

			System.out.print("Prime numbers from 1 - 100 are : \n" + primeNumber);

			

		

		

		}

		

}

In this case it`s enough to find only one number that divides our number because we divide it only starting from 2, so we don`t test it with 1 because we know that any number can be divided by 1 and we also don`t test it for numbers that are larger than the half of the number.
For example if we are checking the number 7: it`s a prime number
it`s divided by 1 like any other number so we don`t need to test it
and it`s divided by 7, but again this is something that we don`t need to test, each number can be divided by itself
and we also don`t need to test it for numbers that are bigger than it`s half, in our case 4, we can be sure that no number can be divided by a number that is bigger than it`s half

[Gman]

Not sure what you mean fread, can you explain more pls.

fread said:

If my math is correct you only need to check up to square_root(n) where n is the 100 in this case.

[Sinipull]

sqrt(100) = 10
Which mean that you only need to check if the number divides by any prime below the 10.

For example if a number 64 divides evenly by 4. 64/4 = 16 then you already know that 64/16 is also 4.
The same reason is why you don't need to divide anything above the sqrt line.

For example let's take a prime number 103. sqrt(103) = 10.14
103 / 2 == 51.5
103 / 3 == 34.333
103 / 5 == 20.6
103 / 7 == 14.7
103 / 11 == 9.36 < sqrt(103)

2,3,5,7,11 are previously found primes.

There's no need to check further, because we know that the answer is going to descend until it becomes close to 0 and there can not be any answers between, because we already checked everything from 2 to 11. Which means 103 must be prime

[fread]

Ok, I think I may have misguided you or at least added to your confusion.

I'LL review you code. You have two loops.
One counting up to n which is 100 in this case.
Another which test for the prime property. This loop counts down for each i value it receives


The inner loop:

for(x =i; x>=1; x--)
  {
        if(i  %  x == 0)
        {
              ctr = ctr + 1;
         }
  }

What you are doing here is: for each number you receive (i), you test for prime quality.
You do this by checking every value from i to 1 inclusive to see if it evenly divides i. This is ok but, if your limit for n was large, this method will be very slow. But I guess it is ok for 100.

What Sinipull was saying here:

Quote

Also, there's no need to check any primes above the i/2 line. For example 100 can not evenly divide by any number over 50, because it's certain, that the answer is less than 2.

is basically this:
Think of the number 10. There is no number greater than 5 that can divide 10 Evenly.
Think of the number 18. There is no number greater than 9 that can divide 18 Evenly.
Then you only need to check for divisors half the size of i and go down; cutting your prime test by half for each value i you receive.
Which would make you loop look more like this:

for(x = (i / 2) + 1 ; x>=1; x--)
{
       if(i % x == 0)
       {
            ctr = ctr + 1; /* check for 1 in the outer loop; two or more would be not prime */
       }
 }

Play around with a few numbers to get the gist.

When i said:

Quote

If my math is correct you only need to check up to square_root(n) where n is the 100 in this case.

I was speaking generally about solving the prime number problem, in terms of making you algorithm more efficient.
In your case; if you were testing 64 for the prime quality and you started from square_root(n) and decremented like you did in your code
you may end up with incorrect results.
i.e square_root(64) = 8 ---> You check 8 7 6 5 4 3 2 1. But numbers like 16 and 32 evenly divide 64.

A better approach for solving the prime problem is using Sieve of Eratosthenes - Wikipedia, the free encyclopedia.

I have a copy so ill save you some of the trouble.

//isPrime.c
#include <stdio.h>
#include <math.h>
#define N     100              /* limited only by memory size   */
#define SQRTN ((long) sqrt(N))


int generatePrimes(int  prime[])
{
 /* ------------------------------------------------------------------------- *
 * This is the classic prime sieve of Eratosthenes - a simple algorithm      *
 * that finds all the prime numbers between 2 and the constant 'N'.          *
 * n is prime <=> prime[n] == 1                                                                          *
 * Name            : sieve.c  (Sieve of Eratosthenes)                        *
 * Author          : Steve Park & Dave Geyer                                 *
 * Language        : ANSI C                                                  *
 * Latest Revision : 9-15-96                                                 *
 * Adapted by       :                                        *
 * ------------------------------------------------------------------------- */

  int temp;
  long i;                             /* index of possible primes      */
  long s;                             /* step index                    */

  prime[0] = 0;                       /* initialize the sieve */
  prime[1] = 0;
  for (i = 2; i <= N; i++)
    prime[i] = 1;

  for (i = 2; i <= SQRTN; i++)         /* search all possibilities       */
    if (prime[i])                      /* if n is prime,                 */
      for (s = 2; s <= (N / i); s++)   /* 2n, 3n, 4n ...  can't be prime */
        prime[s * i] = 0;

}

int main()
{
    int prime[N + 1];
    int i;

    generatePrimes(prime);
    for(i = 0; i <= N; i++)
        if(prime[i]) printf(" % d",i);
    printf("\n");
    return 0;
}

I'm hoping this helps.

---------- Post added at 01:41 PM ---------- Previous post was at 01:37 PM ----------

Edit: You can translate that C to java without to much taught.