Sahat Yalkabov - 2 months ago 13

C++ Question

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++)`

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.)

Answer

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.