prime numbers

[mcgrim8]

this code is supposed to iterate through all consecutive numbers from 2 to 100 and should print all the prime numbers. What I get is instead a long list of repeated prime numbers with non-prime numbers showing up occasionally in between.
I am not so sure how to fix this.

  #include "pch.h"
#include <iostream>

using namespace std;

int main()
{
	
	for (int i = 3; i <= 100; i++)
	{
		for (int n = 2; n < i; n++)
		{
			if (i%n == 0)
			{
				break;
			}
			else
			{
				cout << i << endl;
			}
		}
	}
	return 0;
}

[George P]

#include <iostream>

int main()
{
   for (int i = 3; i <= 100; i++)
   {
      bool prime = true;

      for (int n = 2; n < i / 2 + 1; n++)
      {
         if (i % n == 0)
         {
            prime = false;
            break;
         }
      }

      if (prime)
      {
         std::cout << i << ' ';
      }
   }

   std::cout << '\n';
}

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

You can also do the prime check in a function:

#include <iostream>

bool is_prime(int);

int main()
{
   for (int i = 3; i <= 100; i++)
   {
      if (is_prime(i))
      {
         std::cout << i << ' ';
      }
   }

   std::cout << '\n';
}


bool is_prime(int num)
{
   for (int n = 2; n < num / 2 + 1; n++)
   {
      if (num % n == 0)
      {
         return false;
      }
   }

   return true;
}

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

[mcgrim8]

I can see that you pretty much rewrote the whole code from scratch.
I appreciate your help, but do you think there is a way to slightly change my code
in order to obtain your same outcome, without using booleans? If I am a way off the track and is not possible, I understand.

[lastchance]

You need some boolean to record primeness - your code was printing out regardless.

Note that 2 is prime as well.

Your search range could be reduced to n <= sqrt(i), since if there is any proper factor then one must be in that range. However, I've left it for now.

#include <iostream>
using namespace std;

int main()
{
   for (int i = 2; i <= 100; i++)            // 2 is prime as well!
   {
       
      bool isPrime = true;                   // until told otherwise ...
      for (int n = 2; n < i; n++)            // you could actually reduce this to n <= sqrt(i) if desired
      {
         if (i%n == 0)
         {
            isPrime = false;                 // you need to update this
            break;                           // no need to check any more
         }
      }
      
      if ( isPrime ) cout << i << endl;      // you need that boolean to gauge primeness
   }
}

[Ganado]

Go through your first post's code, line by line. Notice the logic within the inner for loop. n begins at 2. You then check if i % 2 == 0 (i.e. "is i even"). If i is even, you return false. If it is not even, you print it.

Essentially, you're checking if the number is even, and printing it if it isn't. (And then printing every other number that it isn't divisible by.) Do you see how this is different than checking if it's prime?

[dhayden]

With minimal changes to your original code:
- start i at 2 instead of 3
- Declare n inside the outer loop and use its value after the inner loop to tell if the number was prime.

As others have stated, your algorithm is very inefficient because you check many more factors than necessary.

#include "pch.h"
#include <iostream>

using namespace std;

int main()
{
	
	for (int i = 2; i <= 100; i++)
	{
		int n;
		for (n = 2; n < i; n++)
		{
			if (i%n == 0)
			{
				break;
			}
		}
		if (n == i)
		{
			cout << i << endl;
		}
	}
	return 0;
}

[MikeStgt]

Using GOTO is bad habit, I know. But in this dull case and the lack of C++ to tell which one of nested loops to iterate I can not resist to eliminate the flag in lastchance's suggestion.

#include <iostream>
using namespace std;

int main()
{
   for (int i = 2; i <= 100; i++)           // 2 is prime as well!
   {
      for (int n = 2; n < i; n++)           // you could actually reduce this to n <= sqrt(i) if desired
         if (i%n == 0) goto next_i;
      cout << i << endl;                    // you need no boolean to gauge primeness
next_i:;
   }
}

But please, do not use this much farther than up to 100.

Edit: corrected a comment.
Note: I code transparently the jump otherwise concealed in if (isPrime)

[Niccolo]

int main()
{
   for (int i = 2; i <= 100; i++)           // 2 is prime as well!
   {
      for (int n = 2; n < i; n++)           // you could actually reduce this to n <= sqrt(i) if desired
      {
         if (i%n != 0)
         { cout << i << endl; 
         }
         else
         { break;
         }
     }
   }
}

Though I write it more expanded than required, goto wasn't necessary here

[MikeStgt]

Though I write it more expanded than required, goto wasn't necessary here

Could you please explain what you do better than the OP?

[highwayman]

What if we take MikeStgt’s code and simply replace the goto with a continue.

#include <iostream>
using namespace std;

int main()
{
   for (int i = 2; i <= 100; i++)           // 2 is prime as well!
   {
      for (int n = 2; n < i; n++){           // you could actually reduce this to n <= sqrt(i) if desired
         if (i%n == 0){continue; }
      cout << i << endl;                    // you need no boolean to gauge primeness
      }
   }
}

That should work. :p

[dutch]

highwayman wrote:

That should work. :p

Nope. The continue continues the loop that it's in.

Try this.

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char **argv) {
    int limit = 100;
    if (argc == 2) limit = stoi(argv[1]);
    if (limit < 2) return 0;
    cout << 2 << ' ';
    for (int n = 3; n <= limit; n += 2) {
        int d = 3;
        for ( ; d * d <= n && n % d; d += 2) ;
        if (d * d > n) cout << n << ' ';
    }
    cout << '\n';
}

[highwayman]

Slightly unrelated question: why do you have
int main(int argc,char **argv)? What does that do?

[dutch]

Command Line Parameters | http://www.cplusplus.com/articles/DEN36Up4/

So if you run it as: program_name 1000
it will print primes up to 1000 instead of 100.

[Zaap]

With this code you iterate only though the prime numbers.

vector<int> prime;
bool isPrime;
prime.push_back(2);
for(int i(3);i<limit;i+=2){
    isPrime=true;
    for(int k(0);k++<prime.size();){
        if(i%prime[k]==0){
            isPrime=false;
            break;
        }
    }
    if(isPrime) prime.push_back(i);
}

//disp
for(int i(0);i<prime.size();++i) cout<<prime[i]<<endl;

[dhayden]

MikeStgt's solution would benefit from a language change that I've always thought would be helpful. The idea is to let you break (or continue) an outer loop by specifying the constructs that you want to break/continue from:

#include <iostream>
using namespace std;

int main()
{
   for (int i = 2; i <= 100; i++)           // 2 is prime as well!
   {
      for (int n = 2; n < i; n++)           // you could actually reduce this to n <= sqrt(i) if desired
         if (i%n == 0) continue for for; // continue not the inner for loop, but the outer one
      cout << i << endl;                    // you need no boolean to gauge primeness
   }
}

More specifically, break and continue could be followed by 1 or more for, do, or while keywords (or switch in the case of break). The keywords tell the compiler which construct the break/continue applies to by listing them from inner to outer.

This has the added advantage of helping to ensure that you're breaking/continuing the right structure. Beginners sometimes put a break inside a switch, thinking it will break out of an enclosing for loop.

If no keyword follows the break/continue then the behavior is the same as today (break/continue the inner most construct).

[MikeStgt]

MikeStgt's solution would benefit from a language change that I've always thought would be helpful.

Would be helpful? It definitely is of great help. I know it from REXX with its loop changer iterate [name] and leave [name]. The [optional] name specifies which one of nestet loops is concerned. To implement this in C++ loops should be identifiable by name or other methods (the loop-determing variable for example as in REXX -- but for loops in C++ are so much "vicissitudinous", or variable?).
So nested-loops-aware break and continue in C++2059 earliest.

[jonnin]

its just syntactic sugar for the goto approach, though?

[dhayden]

its just syntactic sugar for the goto approach, though?

No more than break or continue are syntactic sugar for a goto in the first place.

[jonnin]

Fair enough.

[Zaap]

I just wrote an algo to find all the prime numbers before a lim value.

On my PC it takes 68s with a lim of 100 000 000.

#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>

double stockPrimeV3(const int& lim){
    time_t beg=time(0);
    vector<int> p;
    p.push_back(2);
    for(int i(3);i<lim;i+=2){
        bool first(true);
        double rac=sqrt(i);
        for(int k(1);k<p.size() && p[k]<=rac;++k){
            if(i%p[k]==0){
                first=false;
                break;
            }
        }
        if(first) p.push_back(i);
    }
    //for(int i(0);i<p.size();++i) cout<<p[i]<<endl;
    return difftime(time(0),beg);
}

NOTE : if you uncomment the cout, it becomes slower of course.