이게뭐야? 위키피디아 쉽게 말하면, 소수를 찾는 방법이다. 소수라 함은 그 수의 약수가 1과 자기 자신만을 가지는거다. 파이썬 구현 어따씀? https://codeforces.com/contest/1332/problem/B
Algorithm Tag: 수학
사전지식 약수 12와 28의 약수는 ? 12의 약수 => 1 2 3 4 6 12 28의 약수 => 1 2 4 7 14 28 서로소 공약수가 1밖에 없는 두수를 서로소 관계에 있다고 한다. 예를들어, 17과 8은 서로소 관계에 있다. 공약수가 1밖에 없기 때문이다. 최대공약수 두 수의 공약수중 가장 큰것. 12와 28의 최대공약수는 4이다. 2와 4둘중에 […]
첫번째 방법 소요시간 : 6.5초 두번째 방법 (예를들어) 12의 약수 [1, 2, 3, 4, 6, 12] 중 자신을 제외하고 가장 큰 약수는 12의 절반인 6이니까, 6까지만 12를 1~6으로 나누었을때 나머지가 0인지를 확인해보면 된다. 7~11은 어차피 약수가 아니니까 안나눠봐도 된다는 소리다. // -> 소수점을 버린다 소요시간 : 3.29초 세번째 방법 12에 루트를 씌운 값까지만 루프를 돌리면 […]