You need to know if the number is simple. I tried to take the first solution from here ( Is the number simple ) and stuff it into my code, but then it turns out that 1 is simple, 4 is simple, but it is not. Please do not need complex algorithms that supposedly increase performance, not before me now. I want to understand why my code does not work (skips 4k, for example). And since I took the code from that author, I wonder why his answer is positive.

#include <stdio.h> int main() { bool simple = true; int n; scanf_s("%d", &n); for (int i = 2; i < sqrt(n); i++) { if (n == 1) simple == false; if (n % i == 0) { simple = false; return 0; } } if (simple) printf("YES"); else printf("NO"); return 0; }
  • I quote a comment from the same answer: должно быть i<=sqrt(n), иначе квадрат простого числа тоже будет простым. - Shadasviar

2 answers 2

Well, let's break your code ...

 #include <stdio.h> int main() { bool simple = true; int n; scanf_s("%d", &n);

So far, everything is logical.

  for (int i = 2; i < sqrt(n); i++) {

So, if n is the square of a prime number (by the way, where is #include <math.h> ?), Then this prime number is not checked (it is not less, but equal to the square root). For example, for 4 this cycle will not be executed, since 2 no less than 2.

  if (n == 1) simple == false;

If n is one, compare simple and false . Why - it is not clear.

  if (n % i == 0) { simple = false; return 0; }

If n is divisible by i , assign simple to false and terminate the program.

  }

The cycle is over. simple never changed (where it changed, the program ends right there), so that it is true . So the code

  if (simple) printf("YES"); else printf("NO"); return 0; }

Displays just YES , even without carriage return. Code with NO output is never executed.

Is the code parsed? Why doesn't it work - there are no more questions?

  • I understood! Thank you so much for the detailed analysis, I laid everything out for myself, now you can be wondering how to make it faster :) - Ivan Blohin
  • By the way, in VS 15 sqrt worked without connection. But when I uploaded to the site for verification - a compilation error. It's a shame. - Ivan Blohin
  • Well, if you are satisfied with the answer - mark it as accepted :) And faster - you can start by checking only odd ones. or those that have the form 6n+1 or 6n-1 (2 and 3 should be checked separately). I rewrote the loop condition as i*i <= n . Even faster - at least at least some piece of the table of prime numbers, if not in the process of calculating, then simply flashing in the program ... - Harry

Once your cycle starts with 2

 for (int i = 2; i < sqrt(n); i++) {

then at least 1 should immediately be excluded from prime numbers. It also does not make sense to check for even numbers whether they are simple or not. Therefore, in the cycle it is enough to consider odd numbers as divisors.

In this cycle

 for (int i = 2; i < sqrt(n); i++) { if (n == 1) simple == false; if (n % i == 0) { simple = false; return 0; } }

invalid loop condition i < sqrt(n) . Must be at least i <= sqrt(n) . At the beginning of the cycle, every time there is an extra check of the variable n for equality 1. And besides, there is an incomprehensible exit from the program.

Use the following approach

 int n; scanf_s("%d", &n); bool prime = n == 2 || (n % 2 && n != 1); for (int i = 3; prime && i <= n / i; i += 2) { prime = n % i; }

Here is a simple demonstration program showing this approach.

 #include <iostream> int main() { for (unsigned int n = 1; n <= 100; n++) { bool prime = n == 2 || (n % 2 && n != 1); for (unsigned int i = 3; prime && i <= n / i; i += 2) { prime = n % i; } if (prime) std::cout << n << ' '; } std::cout << std::endl; }

The output of the program to the console:

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