[BOJ] 1016번 제곱 ㄴㄴ수

복기

역을 통해 답을 구할 수 있는지 생각해보자.

코드

• C++ 17

#include <stdio.h>   using ll = long long;   bool IsChecked[1000001]; bool IsSquare[1000001];   int main() {     ll min, max;     scanf("%lld %lld", &min, &max);          // 제곱 ㄴㄴ수는 너무 많으므로     // 답의 개수 중 제곱수를 제외한다.     ll ans = max - min + 1;     for (ll i = 2; i * i <= max; ++i)     {         // 이미 검사한 수라면 건너뛴다.         if (IsChecked[i])             continue;           // 중복으로 검사하지 않도록 체크한다.         for (ll j = i; j * j <= max; j += i)             IsChecked[j] = true;           // 제곱수를 뺀다.         ll square = i * i;         for (ll j = ((min - 1) / square + 1) * square; j <= max; j += square)         {             if (IsSquare[j - min] == false)             {                 IsSquare[j - min] = true;                 --ans;             }         }     }       printf("%lld", ans); }

• C# 6.0

using System;   namespace Csharp {     class Program     {         static bool[] IsChecked = new bool[1000001];         static bool[] IsSquare = new bool[1000001];           static void Main(string[] args)         {             var inputs = Console.ReadLine().Split();             long min = Convert.ToInt64(inputs[0]);             long max = Convert.ToInt64(inputs[1]);               long ans = max - min + 1;             for (long i = 2; i * i <= max; ++i)             {                 if (IsChecked[i])                     continue;                   for (long j = i; j * j<= max; j += i)                     IsChecked[j] = true;                   long square = i * i;                 for (long j = ((min - 1) / square + 1) * square; j <= max; j += square)                 {                     if (IsSquare[j - min] == false)                     {                         IsSquare[j - min] = true;                         --ans;                     }                 }             }               Console.WriteLine(ans);         }     } }

• Python 3

from sys import stdin input = stdin.readline   min, max = map(int, input().split()) isChecked = [False] * 1000001 isSquare = [False] * 1000001   ans = max - min + 1 for i in range(2, 1000001):     if i ** 2 > max:         break          if isChecked[i]:         continue       for j in range(i, 1000001, i):         if j ** 2 > max:             break         isChecked[j] = True       square = i ** 2     minimum = ((min - 1) // square + 1) * square     for j in range(minimum, max + 1, square):         if isSquare[j - min] == False:             isSquare[j - min] = True             ans -= 1   print(ans)