[BOJ] 1456_거의 소수

거의 소수

문제 링크: https://www.acmicpc.net/problem/1456

1456번: 거의 소수

 

3차 도전 성공

 

사실상 2차 도전에서 성공했던 것이다.
2차 도전에서 temp에 n^k를 저장하는 temp *= s;가 문제였던 것이다.
이를 long long으로 cast 해주니까 정답으로 처리가 되었다.
소수 문제와 오버플로우 처리를 위한 문제였다.

 

• 정답 코드

    #include<iostream>
    using namespace std;
  
    long long A, B;
    int a[10000001];
    long long size_ = 0;
  
    void primeNumber() {
  
        for (int i = 2; i < 10000001; i++) {
            a[i] = i;
        }
  
        for (int i = 2; i < 10000001; i++) {
            if (a[i] == 0) continue; 
  
            for (int j = 2 * i; j < 10000001; j += i) {
                a[j] = 0;
            }
        }
    }
  
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
        primeNumber();
  
        cin >> A >> B;
  
        for (long long s = 2; s < 10000001; s++) {
            if (s * s > B)
                break;
  
            if (a[s] != 0) {
                long long temp = s * s;
                while (temp <= B) {
                    if (A <= temp)
                        size_++;
                    temp = (long long)s*temp;
                    if (temp % s != 0)
                        break;
                }
            }
        }
  
        cout << size_;
        return 0;
    }

1차 도전

입력 받은 A, B를 ROOT 를 씌운 후 0~(B-A) 사이에 있는 모든 소수들의 수를 구한다.
그 후 해당 소수들의 n^k을 함으로써 최대 (B-A)의 값을 넘기는지 확인한다.
넘지 않는 수들을 카운트 하여 출력한다.
해당 소수의 개수를 구하는 방식은 에라토스테네스의 체를 이용한다.

 

하지만 이 방법은 일정 구간에서 소수가 규칙적으로 존재할 때 가능한 경우이다.
이를 간과한체 해당 알고리즘을 구현했기에 틀렸다고 나온다.
소수는 아직 규칙이 존재하지 않기에 해당 알고리즘은 틀렸다.

 

• 미해결 코드

    #include<iostream>
    #include<vector>
    #include<math.h>
    using namespace std;
  
    vector<int>primeNumbers;
    int A, B;
    int a[1000001];
    int size_ = 0;
  
    void primeNumber(int rootA, int rootB) {
        int number = rootB - rootA + 1;
  
        // 1. 배열을 생성하여 초기화한다.
        for (int i = 2; i <= number; i++) {
            a[i] = i;
        }
  
        // 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
        // (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
        for (int i = 2; i <= number; i++) {
            if (a[i] == 0) continue; // 이미 지워진 수라면 건너뛰기
  
            // 이미 지워진 숫자가 아니라면, 그 배수부터 출발하여, 가능한 모든 숫자 지우기
            for (int j = 2 * i; j <= number; j += i) {
                a[j] = 0;
            }
        }
  
        // 3. 2부터 시작하여 남아있는 수를 모두 출력한다.
        for (int i = 2; i <= number; i++) {
            if (a[i] != 0) primeNumbers.push_back(a[i]);
            //printf("%d ", a[i]);
        }
  
        for (int s = 2; !primeNumbers.empty(); s++) {
            for (int i = 0; i < primeNumbers.size(); i++) {
                int temp = pow(primeNumbers[i], s);
                if (temp > B-A) {
                    for (int k = primeNumbers.size() - 1; k >= i; k--)
                        primeNumbers.pop_back();
                    break;
                }
                size_++;
            }
        }
    }
  
    int main() {
  
        cin >> A >> B;
        int rootA = sqrt(A);
        int rootB = sqrt(B);
        cout << rootA << " " << rootB << endl;
        primeNumber(rootA, rootB);
  
  
      cout << size_ << endl;
      return 0;
  }

---

 

2차 도전

이번에는 모든 소수를 구해두고 각 소수마다 그 값을 k승을 한다.
그리고 그 값을 A와 B사이인지 확인한다.
또한 범위가 벗어남을 방지하기 위한 코드를 삽입하고 제출했다.
단순하게 짜보았다.
그런데 아직 틀린답...

 

• 미해결 코드

    #include<iostream>
    using namespace std;
  
    vector<int>primeNumbers;
    int A, B;
    int a[10000001];
    int size_ = 0;
  
    void primeNumber(int rootA, int rootB) {
        for (int i = 2; i < 10000001; i++) {
            a[i] = i;
        }
        for (int i = 2; i < 10000001; i++) {
            if (a[i] == 0) continue;
            for (int j = 2 * i; j < 10000001; j += i) {
                a[j] = 0;
            }
        }
  
      for (int s = 2; s<10000001; s++) {
          if (s * s > rootB)
              break;
  
          if(a[s] != 0) {
              int temp = s * s;
              while (temp <= rootB) {
                  if (rootA <= temp)
                      size_++;
                  temp *= s;
                  if (temp % s != 0)
                      break;
              }
          }
      }
  }
  
  int main() {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL); cout.tie(NULL);
  
      cin >> A >> B;
      primeNumber(A, B);
  
      cout << size_ << endl;
      return 0;
  }    for (int s = 2; s<10000001; s++) {
          if (s * s > rootB)
              break;
  
          if(a[s] != 0) {
              int temp = s * s;
              while (temp <= rootB) {
                  if (rootA <= temp)
                      size_++;
                  temp *= s;
                  if (temp % s != 0)
                      break;
              }
          }
      }
  }
  
  int main() {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL); cout.tie(NULL);
  
      cin >> A >> B;
      primeNumber(A, B);
  
      cout << size_ << endl;
      return 0;
  }