소수 찾기2

• 백준 알고리즘 1015번: 제곱 ㄴㄴ 수 문제 정보 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 핵심 에라토스테네스의 체 알고리즘을 활용하여 해당 범위 내에 있는 제곱 ㄴㄴ 수를 찾아낸다 여기서 제곱 ㄴㄴ 수란, 1보다 큰 제곱수로 나누어 떨어지지 않는 수이다. 1부터 10까지의 제곱 ㄴㄴ 수를 알아보면 1 2 3 (4) 5 6 7 (8) (9) 10 4(2의 제곱) 으로 나누어지는 4, 8은 제곱 ㄴㄴ 수가 아니고, 9(3의 제곱) 으로 나누어지는 9는 제곱 ㄴㄴ 수가 아니므로 이를 제외한 나머지 숫자들이 제곱 ㄴㄴ 수가 된다 .. 알고리즘/Java 2023. 9. 6.

• 백준 알고리즘: 1978번 소수 찾기 문제 정보 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 핵심 소수를 구하는 방법을 알면 된다 정수 N을 2부터 N-1까지 나누었을 때 나누어지는 수가 없다면 소수라고 할 수 있다 이 문제의 경우 주어지는 수가 1,000 이하로 정해져 있고, 수가 비교적 작기 때문에 직접 주어지는 N을 2 ~ N-1 으로 하나하나 나누어서 소수인지 아닌지를 판별하면 되지만 수가 커지는 경우는 에라토스테네스의 체 알고리즘을 사용하여 풀이해야 한다 나는 에라토스테네스의 체 알고리즘을 사용하여 풀이하였다 에라토스테네스의 체에 관한 내용은 아래 참고에 링크를 달아두었으니, 모른다면 확인하면 좋을것 .. 알고리즘/Python 2023. 6. 19.