[백준][1016번][수학] 제곱 ㄴㄴ수

제곱 ㄴㄴ 수

https://www.acmicpc.net/problem/1016

<코드>

#include <stdio.h>
long long numbers[1000001];
long long prinum[10000];
 
int main(void){
 
    long long max, min;
    long long num;
 
    int prinum_num = 0;
    int count = 0;
 
    scanf("%lld %lld", &min, &max);
 
 
 
    for (long long i = 2; i*i <= max; i++){
 
 
        long long x = min / (i*i);
        if (min % (i*i) != 0)
            x++;
 
        while (x*(i*i) <= max){
            numbers[x*(i*i) - min] = 1;
            x++;
        }
 
    }
    for (int i = 0; i <= max - min; i++){
        if (numbers[i] == 0)
            count++;
    }
 
 
    printf("%d\n", count);
    return 0;
 

<문제 푼 요령>

 1. 에라토스테네스 체를 사용한다. 

 2. 문제의 핵심은 min + 1,000,000 즉 저장되여야 할 배열의 숫자가 한정적이다.

 3. 탐색을 min ~ max 까지만 하면된다. 

 4. 탐색하는 숫자의 범위는 i는 2부터 max >= i*i 까지 탐색을 해서 채워나간다.

 5. 마지막에 남는 숫자들이 소수 ㄴㄴ 수이다.

 6. 소수만 이용해서 풀면 더 빠른 시간복잡도가 나올거 같다.