Thread: Printing Prime Numbers from 1 to 300.

Code:

#include<stdio.h>
main()
{
	int number, i;

	for (number=2;number<=300;number++)
	{
		for (i=2; i < number ; i++)
		{
			if (number%i==0)
				break;
			else 
				printf("\n%d", number);		
			
		}
		
		continue;
						
				
	}

}

Trying to print the first 300 Prime Numbers.

Here's the program that I made..

Now for some reason unknown to me..it is not giving out the desired output..

Can anybody point out the mistake?

>it is not giving out the desired output..
Let me guess. You're getting lots of duplicates.

>Can anybody point out the mistake?
Do a paper run of the program. You'll easily be able to find the problem if you work through your program step by step. I could point out the mistake, but you wouldn't learn anything about debugging if I did.

>main()
int main ( void ). You also need to return a value at the end. 0 is the normal success value.

>continue;
This is redundant. The loop will continue anyway.

I at least took care of the duplicates..but there's one more problem!

Every number divisible by 5 is also there in the list!

Also, how do I take care of the number 2?
It is also not there on the list!

Code:

#include<stdio.h>
main()
{
	int number, i;

	for (number=2;number<=300;number++)
	{
		for (i=2; i <number; i++)
		{
			if (number%i == 0)
			{
				break;
			}
			else
			{
				printf ("\n%d", number);
				break;
			}

		}
		
	}
}

>Every number divisible by 5 is also there in the list!
May I suggest an is_prime function? A simple function that takes a number and returns either 0 or 1 depending on whether it's prime or not will save you a lot of headaches. The biggest problem you have is coordinating the two loops to do what you want. If you can do the following, it would be much easier, ne?

Code:

int main ( void )
{
  int i;

  for ( i = 2; i < 300; i++ ) {
    if ( is_prime ( i ) )
      printf ( "%d\n", i );
  }

  return 0;
}

Look up the definition of Prime (again).
In fact, look at Eratosthenes sieve (google for it).

Okay..this is my new program..as lousy as it is..but it works!!!

Code:

#include<stdio.h>
main()
{
	int number, i;

	for (number=1;number<=300;number++)
	{
		for (i=2; (i<number) || (i==number) ; i++)
		{
			if (i==number)
			{
				printf ("\n%d", number);
			}

			if (number%5==0)
			{
				break;
			}


			if (number%i == 0 )
			{
				break;
			}
			else
			{
				printf ("\n%d", number);
				break;
			}

		}
		
	}

}

@mako

if you start with number on 2, and with i on 2. Then it should be obvious that number%i is 0...

and you don't need the second break...

Yeah man..I could figure that out.

If I don't put the second break...it gives me a hell lotta duplicates...


@Prelude

Not yet done with the functions man...I suppose they will make things easier...hehe


@Salem

Look up the definition of Prime (again).
In fact, look at Eratosthenes sieve (google for it).

Yeah man..I know the definition of Prime..
I put int quite a lotta effort into this so called "easy" program..but still did not get the wanted result, so I seeked help.

Well..the Eratosthenes sieve thing was great!


Anybody suggesting an improvement in the program ??

>>Anybody suggesting an improvement in the program ??

Yes - get it to work properly!

Here is the output of your program for numbers less than 50:

2
3
7
9
11
13
17
19
21
23
27
29
31
33
37
39
41
43
47
49

Now, last I checked, the following numbers are NOT primes:

9, 21, 27, 33, 39, 49.

Generally, if your code has to look especially at numbers divisible by 5, there's
a design flaw in your approach.

I'd go with Prelude's suggestion to make an isprime function, test it thoroughly
over a range of values easy to spot errors, and fix the program from there.
Also, you should allow the user to enter the upper limit on numbers you want
to test, or even specify the range - allow the user to get primes between any
two numbers.

Lastly:

1. main returns int, and since you are not using command line arguments, the parameter
list should be (void)

2. (i<number) || (i==number) is the same as (i <= number)

3. You can make this program run more efficiently by using (i < ((number/2) + 1)), since
a number cannot be evenly divided by any number greater than half its value

I have tried to do the same thing man...

Code:

for (number=1; number<=300; number++)
{
	for (i=2; i<=number; i++)
	{
         if (i==number)
            { 
               printf("\n%d", number);   /*this basically prints out '2' */
             }

		if (number%i==0)
		{
			break;   /*cuz the number is not prime and no 
			           further checking would be necessary.*/
		}

		else 
		{
			printf("\n%d");  /*the number is indeed prime, and so needs to be printed out!*/

			break; /*people say that this break is redundant 
				   but without this i am getting duplicates of numbers 
				   (and they are not prime too!)*/
		} 
	}
}

I cannot think any further!

For checking if a number is prime or not...i know what needs to be done..

I need to divide the number by a number greater than one and a number less than the number itself..that would be

for (i=2; i<number; i++) OR for (i=2; i<=number-1; i++)

The outer loop would be for (i=2; i<=300; i++)
...to increment the numbers that are gonna be checked for PRIME...


Bottomline..i am outta ideas...(

Originally Posted by duffmckagan

I have tried to do the same thing man...


I need to divide the number by a number greater than one and a number less than the number itself..that would be

Actually, you only need to divide the number by a number between 2 on the lower end and number/2 on the upper end. Dividing by anything more than number/2 is just a waste of cycles....

Because you seem about at wits end, here's something that might work....

Originally Posted by duffmckagan

Code:

printf("1\n");
printf("2\n");

for (number=3; number<=300; number++)
{
        int isPrime = 0;
	for (i=2; i<=number/2; i++)
	{
 		if (number%i==0)
		{
                       isPrime = 0;
			break;   /*cuz the number is not prime and no 
			           further checking would be necessary.*/
		}
                isPrime = 1;
	}

        if (isPrime)
            printf("%d\n",number);
       
}

I

I think that should work. I'm winging it while I'm doing real work here today.... It'll get you closer if it doesn't get you all the way there....

> for (i=2; i<=number/2; i++)
1. you only need to check upto sqrt(number)
2. if you eliminate %2 as a special case, then both the inner and outer loops can increment by 2 each time, not 1