ITeus

이번문제는, 0~N사이의 소수의 개수를 찾는 문제입니다. https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 일단, 소수는 규칙이 없습니다. 때문에, 컴퓨터에서 소수 여부를 확인할라면, N을 나눠서 나머지가 0인 숫자가 있는지를 전부 확인해야합니다 (정확히는 N^(1/2)까지) https://teus-kiwiee.tistory.com/61?category=914262 Prime Numbe..

소수(Prime Number)는 1이외에 어떠한 값으로도 나눠지지 않는(나머지가 없는) Number를 의미합니다. 이런 소수는 암호악에서 주로 사용되며, 매우 큰 Number가 소수인지 소수가 아니면 어떻 값과 곱해지는지를 사용하는 방법이 사용됩니다.(공개키 암호) 컴퓨터가 해당 Number가 소수인지, 소수가 아니면 어떤 값과 곱해지는지 확인하는 방법은 1. 1~Number까지 나눠서, 나눈 나머지를 확인한다 1_1. 만약 나머지가 0이면 1 이외에 나눠지는 값이 있으므로, 소수가 아님 2. Number의 1/2까지 진행 후 알고리즘 종료 Number의 1/2를 넘어가면, 어차피 Number를 나눠도 1보다 작아지기 때문에 의미가 없습니다. 이렇게 되면 O(1/2N) = O(N)의 시간복잡도를 갖는 P..