[백준] 거의 소수 c++

거의 소수 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

19228

4839

3294

23.899%

문제

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

출력

첫째 줄에 총 몇 개가 있는지 출력한다.

제한

• 1 ≤ A ≤ B ≤ 1014

---

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	const int MaxSize = 10000001;

	long min, max;

	cin >> min >> max;

	//배열의 크기가 커 힙에 할당.
	long* A = new long[MaxSize];

	for (int i = 2; i < MaxSize; i++)
	{
		A[i] = i;
	}

	//i는 MaxSize의 제곱근을 넘지 않는다.
	for (int i = 2; i <= sqrt(MaxSize); i++)
	{
		if (A[i] == 0)
		{
			continue;
		}

		//j 증가량에 i를 더해 배수로 게속 더해지도록 한다.
		for (int j = i * 2; j < MaxSize; j += i)
		{
			A[j] = 0;
		}
	}

	int count = 0;

	for (int i = 2; i < MaxSize; i++)
	{
		if (A[i] != 0)
		{
			long temp = A[i];

			
			//변수 표현 범위 초과 오류를 막기 위해 double로 변경 및 나눗셈 처리
			while ((double)A[i] <= (double)max / (double)temp)
			{
				if ((double)A[i] >= (double)min / (double)temp)
				{
					count++;
				}

				temp *= A[i];
			}
		}
	}

	cout << count;

	delete[] A; // 동적 메모리 해제
}

 

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