Print Prime Numbers(using for loop)

[john_hasan]

Friends i have little bit problem in making a c language program.
I have to make a program which prints prime numbers from 1 to 500.
I make this program but with while loop then i was told to make it using for loop, which i tried but failed.
So kindly help me. Thanks
from,
john(pakistan)

[Micko]

No problem, just show us what you manage to do so far...

[john_hasan]

It is my while loop program:

#include<stdio.h>
#include<conio.h>
void main()
{
int count,i=1;
int a;
clrscr();
while(i<=500)
{
count=0;
a=1;
while(a<=i)
{
if(i%a==0)
count++;
a++;
}
if(count==2)
printf("%d\t",i);
i++;
}
getch();
}

[hollystyles]

Here you go. Added for loop in place of while, and commented out the i++ at end of while loop.

Also added int variable col, to print a newline every ten numbers printed to standard out.

#include<stdio.h>
#include<conio.h>

int main(int argc, char *argv[])
{
    int count,i=1;
    int a;
    int col=0;
    
    //while(i<=500)
    for(i=1; i<501; i++)
    {
        count=0;
        a=1;
        
        while(a<=i)
        {
            if(i%a==0)
                    count++;
            a++;
        }
        
        if(count==2){
            printf("%d\t",i);
            col++;
            if(col%10==0)
                printf("\n");
        }  
        //i++;
    }
 
  system("PAUSE");	
  return 0;
}

[Salem]

> I make this program but with while loop then i was told to make it using for loop, which i tried but failed.

So turn

i = 0;
while ( i < 500 ) {
  // do stuff
  i++;
}

To

for ( i = 0 ; i < 500 ; i++ ) {
  // do stuff
}

[hollystyles]

DOH! Salem

Johns' while loop was: less than OR EQUAL to 500.

So change to for i < 501 NOT 500.

This is Johns' future your playing with, pay attention.

[Salem]

I didn't pay any attention to his program, it wasn't formatted with code tags.

All I did was illustrate the relationship between for loops and while loops, and how ridiculously easy it is to convert one into the other.

[shavez_israr]

Friends i have little bit problem in making a c language program.
I have to make a program which prints prime numbers from 1 to 500.
I make this program but with while loop then i was told to make it using for loop, which i tried but failed.
So kindly help me. Thanks
from,
john(pakistan)

int flag=1;
for(int i=2;i<500;i++)      //since 1 and 500 are not prime
{                  
flag=1;
for(int j=2;j<i/2;j++)   //since a no. cannot be divisible by a 
{                                //no. greater than its half.
if(i%j==0)                 //if i is divisible by any no. between 2 & i/2
{
flag=0;
break;
}
}
if(flag==1)
printf("\n",i);
}

[Salem]

> for(int j=2;j<i/2;j++) //since a no. cannot be divisible by a
> { //no. greater than its half.
It's square root of actually, but hey what the heck.

At least it's not the only mistake in your code.

[hollystyles]

Ok here's my best shot. The key rule for a prime number is:

It has precisely two positive integer factors.

So the neatest solution I can think of counts those and quits the for loop as soon as it's found more than 2 or reached half way to n.

Can anyone better it?

#include <iostream>

using namespace std;

static const int MAX = 500;
static const int MIN = 0;
static const int MAXCOL = 10;

bool isPrime(int r);

int main(int argc, char *argv[])
{
    int col = 0;
    int n;
    
    for(n=MIN; n<=MAX; n++)
      if(isPrime(n)){
          cout << n << '\t';
          col++;
          if(col == MAXCOL){
              cout << '\n';
              col = 0;
          }
      }  
      
  system("PAUSE");	
  return 0;
  
}

bool isPrime(int n)
{
    if((n == 0)||(n == 1))
        return false;
        
    int factors = 2;
            
    for(int i=2; i<=((int)n/2); i++){
        if(n%i == 0){
            factors++;
            break;
        }
    }
            
    if(factors == 2)
        return true;
    
   return false;
}

[hollystyles]

Ah it's just occured to me what Salem meant by square root !

A revised edition:

#include <iostream>
#include <cmath>

using namespace std;

static const int MAX = 500;
static const int MIN = 0;
static const int MAXCOL = 10;

bool isPrime(int r);

int main(int argc, char *argv[])
{
    int col = 0;
    int n;
    
    for(n=MIN; n<=MAX; n++)
      if(isPrime(n)){
          cout << n << '\t';
          col++;
          if(col == MAXCOL){
              cout << '\n';
              col = 0;
          }
      }  
      
  system("PAUSE");	
  return 0;
  
}

bool isPrime(int n)
{
    if((n == 0)||(n == 1))
        return false;
        
    int factors = 2;
            
    for(int i=2; i<=((int)sqrt((double)n)); i++){
        if(n%i == 0){
            factors++;
            break;
        }
    }
            
    if(factors == 2)
        return true;
    
   return false;
}

Now if only I could make i++ step in primes!

[iamthwee]

>can anyone better it?

Yes, there are more faster prime number finding Al-Gore-it-hims out there.
http://en.wikipedia.org/wiki/Sieve_of_Atkin

Note I said faster as opposed to efficient. An efficient prime number list finding strategy would be rather elusive.

Also, I'm sure you can think of a much better way to pause the program than using system("PAUSE"); ?

:lol:

[hollystyles]

Also, I'm sure you can think of a much better way to pause the program than using system("PAUSE"); ?

:lol:

Ok whats wrong with system("PAUSE") ?

I

[dude543]

I dont know that high math, but I think I can do better.

bool isPrime(int n)
{
bool prime ;
int  lim;
 
if ( n == 0 || n == 1 || n % 2 == 0)
   return(false);

prime = true;
lim = (int)sqrt(n); 
 
for(int i=3; i<= lim && prime ; i+=2)
       prime =  n % i;
return(prime);
}

[Salem]

> for(int i=2; i<=((int)sqrt((double)n)); i++)
And it would be so much quicker if you didn't call sqrt() on every iteration of the loop!
n is constant (in this function), so it's root is constant also. Calculate it once and store in another variable to compare against.

Also, since 2 is prime, that's an easy case to get rid of, and you can start at 3.

Also, if you start at 3, then you can do i+=2 to only check all the odd numbers from there on.

[hollystyles]

Dude543 yes I like that very much.

Salem good feedback.

So system("PAUSE") then, what gives ? I havn't found anything negative on the internet yet.

Ok I've found it:

http://www.gidnetwork.com/b-61.html

[hollystyles]

Actually dud543 I think this is wrong: || n % 2 == 0) That would return false for 2 which is prime.

[dude543]

Well. I also think that it is wrong.
But poor me, does'nt know wheter 0,1,2 are prime.
I know that prime will divide by himself and one only.
I Guess you are right.
Anyway. is there someway for me to edit the post ?

[hollystyles]

you can't edit a post more than 30 minutes after you posted in this forum.

0 and 1 are not prime. Yes 1 is divisible by 1 and itself, but that's the same thing it's only one factor not two factors so it's not prime.

2 is a special case, it is the only even number that is a prime.

[Bench]

I wouldn't call 2 a special case - it fits the general description perfectly; A number evenly divisible only by 1 and itself. :)

[hollystyles]

I wouldn't call 2 a special case - it fits the general description perfectly; A number evenly divisible only by 1 and itself

Strictly that's not true because 1 is divisible by 1 and itself, but 1 isn't prime. I prefer:

A prime number has precisely two positive integer factors.

[portege]

This should be considerably although I'd bet not noticeably faster.

#include <iostream>
using namespace std;
int main (){
int prim=3, div,i=2;
cout<<1<<" "<<2<<" ";
for (i; i<=500; i++){
div=3;
while(div<=prim/3){
if (prim%div!=0){div+=2;}
else {prim+=2;div=3;}}
cout<<prim<<" ";
prim+=2;}
system("pause");}

Why do you care about the speed anyways?

[~s.o.s~]

Why do you care about the speed anyways?

If the developers didnt care for speed then u wouldn't be conviniently using your favourite OS u are usign right now without atlest swearing atleast 100 times a day regarding the slow loading times.

Dont forget that this is a C/ C++ forum and speed is one of the major merits of this language and bcoz of which it is used to make real time softwares.

Though optimization should be last on ur list but it still is nevertheless an issue to be handled.

EDIT:
@hollystyles: btw 1 is a composite and 2 is a prime number

Here is a convinient and easy to understand way of fiding primes:

int isPrime (int number)
{
    if (number == 2)
        return 1;

    if (number % 2 == 0)
        return 0;

    for (int i = 3; i < number / 2; i += 2)
    {
        if ((number % i) == 0)
            return 0;
    }
    return 1;
}

[portege]

I meant why do you care about thespeed when calculating the first 500. It took me <1 second. :P

[WolfPack]

I meant why do you care about thespeed when calculating the first 500. It took me <1 second. :P

So are you writing two programs?
One that is slow to calculate the first 500
The second that is fast to calculate the rest.

The main objective of the program is to be accurate. After that you should do everything to make it fast as possible under the given restraints. Some restraints are
the clarity of a program
easy maintainability
the extra cost of implementing a more efficient algorithm

Anyway because of time restraints on our part, we can't sometimes make time to provide efficient code in the forum. But if someone else does provide accurate fast code, it is always superior to accurate slow code.

[~s.o.s~]

Mr. Wolf any suggestions to my working code, can it be made better.

int isPrime (int number)
{
    if (number == 2)
        return 1;

    if (number % 2 == 0)
        return 0;

    for (int i = 3; i < number / 2; i += 2)
    {
        if ((number % i) == 0)
            return 0;
    }
    return 1;
}

Thanks in advance.

[portege]

any suggestions to my working code, can it be made better.

Change

i < number / 2

to

i < number / 3

2 is the only number you want that can be divided by two (1+2n)

[WolfPack]

Mr. Wolf any suggestions to my working code, can it be made better.

int isPrime (int number)
{
    if (number == 2)
        return 1;

    if (number % 2 == 0)
        return 0;

    for (int i = 3; i < number / 2; i += 2)
    {
        if ((number % i) == 0)
            return 0;
    }
    return 1;
}

Wan't there a suggestion in a previous reply that searching only upto squareroot of n is enough? replace n/2 with sqrt(n) and it should be much better. There is more information here.

[~s.o.s~]

Thanks a lot for the optimizations both of u.
Completely forgot to take that into consideration.

[Lerner]

To "optimize" it a little further without getting too technical you could keep track of each prime along the way. Then to check if current number is prime just check to see if previous primes up to the square root of the current number are a factor rather than checking all odd numbers less than square root of current number. If none of the previous primes is a factor, then the current number is a prime.