seanrocket17   4년 전

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

simm4256   4년 전

15줄

i*i -> 2*i

seanrocket17   4년 전

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


seanrocket17   4년 전

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

alice   4년 전

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

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


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

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


seanrocket17   4년 전

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

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