C++에서 N보다 작거나 같은 모든 소수 인쇄

이 문제에서는 숫자 N이 주어지고 N보다 작거나 같은 모든 소수를 출력해야 합니다.

주제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -

Input: 10
Output: 2 3 5 7

소수 는 1과 숫자 자체로만 나눌 수 있는 숫자입니다. 예:2, 3.

간단한 접근 방식은 2에서 N까지 반복하고 숫자를 N으로 나누는 것입니다. 숫자가 나누어지지 않으면 소수입니다. 번호를 인쇄하십시오. 숫자가 N이 될 때까지 이 작업을 수행합니다. 이 방법은 그다지 효율적이지 않습니다.

보다 효과적인 접근 방식은 2에서 √N까지 반복하여 소수를 확인하는 것입니다.

예시

#include <bits/stdc++.h>
using namespace std;
bool isPrimeNumber(int n){
   if (n <= 1)
      return false;
   if (n <= 3)
      return true;
   if (n % 2 == 0 || n % 3 == 0)
      return false;
   for (int i = 5; i * i <= n; i = i + 6)
      if (n % i == 0 || n % (i + 2) == 0)
         return false;
   return true;
}
void printPrime(int n){
   for (int i = 2; i <= n; i++) {
      if (isPrimeNumber(i))
         cout<<i<<" ";
      }
   }
int main(){
   int n = 41;
   cout<<"Prime numbers less than or equal to "<<n<<" are \n";
   printPrime(n);
}

출력

41보다 작거나 같은 소수는

2 3 5 7 11 13 17 19 23 29 31 37 41