Sahat Yalkabov - 1 month ago 5
C++ Question

# Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97.

But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop to

`for (int j=2; j<sqrt(i); j++)`
but it did not give me the result I needed.

How would I need to change this code to the way my book wants it to be?

``````int main ()
{
for (int i=2; i<100; i++)
for (int j=2; j<i; j++)
{
if (i % j == 0)
break;
else if (i == j+1)
cout << i << " ";

}
return 0;
}
``````

A prime integer number is one that has
exactly two different divisors,
namely 1 and the number itself. Write,
run, and test a C++ program that
finds and prints all the prime numbers
less than 100. (Hint: 1 is a prime
number. For each number from 2 to 100,
find Remainder = Number % n, where n
ranges from 2 to sqrt(number). \ If n
is greater than sqrt(number), the
number is not equally divisible by n.
Why? If any Remainder equals 0, the
number is no a prime number.)

Three ways:

1.

``````int main ()
{
for (int i=2; i<100; i++)
for (int j=2; j*j<=i; j++)
{
if (i % j == 0)
break;
else if (j+1 > sqrt(i)) {
cout << i << " ";

}

}

return 0;
}
``````

2.

``````int main ()
{
for (int i=2; i<100; i++)
{
bool prime=true;
for (int j=2; j*j<=i; j++)
{
if (i % j == 0)
{
prime=false;
break;
}
}
if(prime) cout << i << " ";
}
return 0;
}
``````

3.

``````#include <vector>
int main()
{
std::vector<int> primes;
primes.push_back(2);
for(int i=3; i < 100; i++)
{
bool prime=true;
for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++)
{
if(i % primes[j] == 0)
{
prime=false;
break;
}
}
if(prime)
{
primes.push_back(i);
cout << i << " ";
}
}

return 0;
}
``````

Edit: In the third example, we keep track of all of our previously calculated primes. If a number is divisible by a non-prime number, there is also some prime <= that divisor which it is also divisble by. This reduces computation by a factor of primes_in_range/total_range.

Source (Stackoverflow)