글 읽기 - help me plz

wowoto9772 6년 전 0

도와주세요..

올바른 솔루션이라고 생각하는데,

물론 틀렸으니 Wrong Answer가 나겠지만,

반례 를 찾고싶습니다..

#include <stdio.h>

int top;

long long P[150000];
bool p[1300003];

int main()
{
	int nxt;
	for (long long i = 2; i*i <= 1300000; i++){
		nxt = i;
		if (!p[i]){
			P[top++] = i*i;
			for (int j = i + i; j <= 1300000; j += i){
				p[j] = true;
			}
		}
	}


	for (long long i = nxt+1; i <= 1300000; i++)if (!p[i])P[top++] = i*i;

	long long n, m;
	while (scanf("%lld %lld", &n, &m) == 2){
		long long ans = m - n + 1;
		for (int i = 0; i < top && P[i] <= m; i++){
			ans -= (m / P[i]) - ((n - 1) / P[i]);
		}
		printf("%lld\n", ans);
	}
}

yukariko 6년 전 0

^{반례는 잘 모르겠고 ans를 구하는 방법이 잘못된겋 같습니다.}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

help me plz

wowoto9772 6년 전 0

yukariko 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말