글 읽기 - 반레가 무엇일까요????

kcl5363 6년 전 0

반례가 뭘까요??

오버플로우도 최대 1000*1000이라서 int 범위에서 해결되는거 같은데 찾아주세요ㅠㅠㅠㅠㅠ

#include <iostream>

using namespace std;
bool B[1001];

int main(){
	int n,k;
	int num;
	int cnt=0;
	bool b=false;
	cin>>n>>k;
	for(int i=2;i<=n;i++){
		if(B[i]==true)continue;
		for(int j=2;j*j<=i;j++){
			if(i%j==0){
				b=true;
				break;
			}
		}
		if(b==false){
			cnt++;
			if(cnt==k)num=i;
			for(int j=i*i;j<=n;j+=i){
				B[j]=true;
				cnt++;
				if(cnt==k)num=j;
			}
		}
		b=false;
	}
	cout<<num<<endl;
	return 0;
}

djm03178 6년 전 1

23번째 줄 루프를 돌 때 나오는 값도 이미 B[j]가 true일 수 있는데, 그 때에도 여전히 cnt가 증가됩니다.

12 6에서 이미 12가 걸러지는데, 12 9에서 또 12가 나옵니다.

kcl5363 6년 전 0

덕분에 해결했습니다!! 와 용케 찾으시네요 ㅎㅎ

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

문제

문제

출처

ICPC

반레가 무엇일까요????

kcl5363 6년 전 0

djm03178 6년 전 1

kcl5363 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말