Yes, I know the algorithm is delusional, but I have stalled and I can’t think of anything, the algorithm should be selectable, iterate over dividers with limitations for efficiency, the question is exactly according to the algorithm.

bool flag = false; for (int j = 3; j < n; j+=2) { double b = sqrt(j); for (int a = 1; a<b; a+=2) { if (j%a == 0) { flag = true; break; } } if (flag) cout << j; }
  • 2
    What is the question? - Vlad from Moscow
  • Your inner cycle starts from 1. And the prime numbers are also divisible by 1. :) - Vlad from Moscow
  • Write what is wrong with your algorithm. - default locale
  • Yes, he just arithmeticizes the progression starting from 3 by doing +2, and now I can't figure out how to arrange the algorithm, what conditions to add, what to change - FFF3_ZE
  • one
    Possible duplicate question: Array of prime numbers in C - Mirdin

2 answers 2

We must not forget 2, put the flag inside the loop, change its logic ... This is if you need a simple search. If you want to speed up, write the found simple ones into an array and check the divisibility only for them.

 int main(int argc, const char * argv[]) { int n = 100; cout << 2 << endl; for (int j = 3; j < n; j+=2) { bool flag = true; if (j%2 == 0) continue; for (int a = 3; a*a <= j; a+=2) { if (j%a == 0) { flag = false; break; } } if (flag) cout << j << endl; } }

Check of divisibility only for simple ones

 int main(int argc, const char * argv[]) { int n = 100; vector<int> primes = { 2 }; cout << 2 << endl; for (int j = 3; j < n; j+=2) { bool flag = true; for(auto i: primes) { if (j % i == 0) { flag = false; break; } if (i*i > j) break; } if (flag) { cout << j << endl; primes.push_back(j); } } }
  • Strange, still superfluous numbers are present, such as 9, 25, 49 - FFF3_ZE
  • Yes, it is necessary to replace a < b with a<=b , corrected, thanks! And in general, removed from there sqrt :) - Harry
  • yes, thank you) - FFF3_ZE

Your inner cycle starts with 1

 for (int a = 1; a<b; a+=2) ^^^^^

Therefore, for any number the condition

  if (j%a == 0)

It will always be true. Therefore, any number you will be simple. :)

In addition, the outer loop starts at 3

 for (int j = 3; j < n; j+=2) ^^^^^

Therefore, your code generally skips a prime number 2.

In addition, you must set the flag variable at each iteration of the outer loop.

Loops can look like the output_primes function of this demo.

 #include <iostream> std::ostream & output_primes( unsigned int n, std::ostream &os = std::cout ) { for ( unsigned int i = 2; i <= n; i++ ) { bool prime = i == 2 || i % 2; for ( unsigned int j = 3; prime && j * j <= i; j += 2 ) prime = i % j; if ( prime ) os << i << ' '; } return os; } int main() { const unsigned int N = 25; for ( unsigned int i = 1; i <= N; i++ ) { std::cout << "Prime numbers less than or equal to " << i << ": "; output_primes( i ) << std::endl; } return 0; }

Its output to the console

 Prime numbers less than or equal to 1: Prime numbers less than or equal to 2: 2 Prime numbers less than or equal to 3: 2 3 Prime numbers less than or equal to 4: 2 3 Prime numbers less than or equal to 5: 2 3 5 Prime numbers less than or equal to 6: 2 3 5 Prime numbers less than or equal to 7: 2 3 5 7 Prime numbers less than or equal to 8: 2 3 5 7 Prime numbers less than or equal to 9: 2 3 5 7 Prime numbers less than or equal to 10: 2 3 5 7 Prime numbers less than or equal to 11: 2 3 5 7 11 Prime numbers less than or equal to 12: 2 3 5 7 11 Prime numbers less than or equal to 13: 2 3 5 7 11 13 Prime numbers less than or equal to 14: 2 3 5 7 11 13 Prime numbers less than or equal to 15: 2 3 5 7 11 13 Prime numbers less than or equal to 16: 2 3 5 7 11 13 Prime numbers less than or equal to 17: 2 3 5 7 11 13 17 Prime numbers less than or equal to 18: 2 3 5 7 11 13 17 Prime numbers less than or equal to 19: 2 3 5 7 11 13 17 19 Prime numbers less than or equal to 20: 2 3 5 7 11 13 17 19 Prime numbers less than or equal to 21: 2 3 5 7 11 13 17 19 Prime numbers less than or equal to 22: 2 3 5 7 11 13 17 19 Prime numbers less than or equal to 23: 2 3 5 7 11 13 17 19 23 Prime numbers less than or equal to 24: 2 3 5 7 11 13 17 19 23 Prime numbers less than or equal to 25: 2 3 5 7 11 13 17 19 23
  • Thank you, very interesting method. - FFF3_ZE