cyphen156

소수 찾기N이하의 소수를 모두 찾기베이직 기법으로 찾아본 후 시간을 단축할 수 있는 방법을 고려해본다.자세한것은 다음 글을 확인해 보면 좋을 것 같다.https://cyphen156.tistory.com/144 알고리듬#2 소수판정법(primarity Test)소수(Prime Number)를 찾는 방법은 단순하지만 시간이 오래걸린다. 우선 소수란 1을 제외한 어떤 양의 정수가 약수를 1과 자기 자신만을 갖는 수를 말한다. 2, 3, 5, 7, 11, 13 ... 등이 소수다. 보통 제곱cyphen156.tistory.com제약사항0 0 주의 사항없다.CPP풀이소수 찾기_1978_Basic.cpp/** * 백준 소수 찾기_1978_Basic * N이하의 소수를 모두 찾기 * 베이직 기법으로 찾아본 후 시간..

소수(Prime Number)를 찾는 방법은 단순하지만 시간이 오래걸린다. 우선 소수란 1을 제외한 어떤 양의 정수가 약수를 1과 자기 자신만을 갖는 수를 말한다. 2, 3, 5, 7, 11, 13 ... 등이 소수다. 보통 제곱근 판정법이나 가장 효율적이라고 알려진 에라토스테네스의 체를 알고리즘으로사용한다. 본 글에서는 아래로 갈수록 효율적인 방법들을 소개한다. 결정론적 방법 확실하게 소수인지 아닌지를 판단하는 방법 결과가 명확하지만 연산 시간이 길어진다. 일반적인 소수판정법 가장 통상적인 방법은 2부터 시작해서 입력값의 전 까지 모두 나눠보고, 나머지가 존재하는지를 확인하는 방법이다. 이것은 이전글에서 소개한 방법과 동일하게 절반까지만 확인하는 방법 또한 존재한다. 소수판정법_native.C // 일..