Expert: Zlatko - 10/31/2010

Question
Hey. I have this assignment in which i've to generate prime numbers up to a certain limit. Since i'm extremely new to C++ so i have absolutely no idea what's wrong with the program i have written. I have to keep it simple for my understanding. I've written it in Turbo C++ Here:
#include <iostream.h>
#include <conio.h>
void main()
{
clrscr();
int i,j,k;
cout<<"Enter range "<<k;
cin>>k;
for(i=2;i<=k;i++)
{
for(j=2;j<=i;j++)
{
if(i%j!=0)
cout<<i;
}
}
getch();
}

Answer
Hello Meterior

The problem with the program is that it is checking for divisibility, not primeness. You see that the inner (j) loop is printing out i for any case when j does not divide i. Any number (i) will have some number that does not divide it, but that doesn't mean that i is prime. Your inner loop must go through all the candidates and print out i only if all the candidates do not divide i. That means that the cout must be outside of the inner loop. It also means that you need a boolean variable set in the inner loop to keep track if any i%j == 0. If any i%j is 0, then the cout is not done.

Currently, your inner loop goes all the way up to i, and it definitely should not because i always divides i.

Your inner loop can be made faster if you exit it as soon as you find an i%j == 0. Also, notice that the inner loop does not need to go from 2 to i, but rather from 2 to the square root of i.

I hope that helps you to complete your assignment.

Best regards
Zlatko