글 읽기 - 베르트랑 공준 질문이요!!!!!!SOS

seanrocket17 7년 전 0

n<=123456이어서 소수는 넉넉하게 247000까지 에라토스테네스의 체로 구하였습니다. 근데 소수를 모두 출력해보니 대부분은 맞는데 55, 49 등 소수가 아닌 숫자들이 중간중간에 등장하네요. 뭐가 틀렸는지 알려주세요.ㅠㅠ!!!!

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
bool prime[247000];

int main()
{
    for (int i = 0; i < 247000; i++)
        prime[i] = true;
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i < 247000 && prime[i]; i++){
        for (int j = i * i; j < 247000; j += i)
            prime[j] = false;
    }
    while (1){
        int n, cnt = 0;
        scanf("%d",&n);
        if (n == 0)
            break;
        for (int i = n + 1; i <= n * 2; i++)
            cnt += prime[i];
        printf("%d\n",cnt);
    }
}

simm4256 7년 전 0

15줄

i*i -> 2*i

seanrocket17 7년 전 1

근데 어차피 i * 2 에서 i * (i - 1)에서 얘네 다 합성수니까 i * i 로 하는게 시간복잡도를 줄이는 것으로 알고 있는데........

seanrocket17 7년 전 0

2 * i로 바꿔도 출력이 같네요.....ㅠㅠ

alice 7년 전 0

이 문제같은 경우, i가 246999까지 도달할 수 있으므로 자료형의 최대값을 넘길 수 있습니다. (예: 246999 * 246999)

따라서 안쪽 for문의 i * i 는 i * 2로 바꾸는 것이 좋습니다.

그리고 바깥쪽 for문의 prime[i]라는 조건을 if문으로 처리해주셔야 합니다.

작성자님이 올리신 코드는 prime[i]가 false일 경우 아예 루프를 벗어나버립니다.

for (int i = 2; i < 247000; i++) {
		if (prime[i]) {
			for (int j = i * 2; j < 247000; j += i)
				prime[j] = false;
		}
	}

seanrocket17 7년 전 0

맞았어요!!!!감사합니다!!!!!!!!!!

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

문제

문제

출처

ICPC

베르트랑 공준 질문이요!!!!!!SOS

seanrocket17 7년 전 0

simm4256 7년 전 0

seanrocket17 7년 전 1

seanrocket17 7년 전 0

alice 7년 전 0

seanrocket17 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말