복습노트 복습노트

간단히 말하면 어떤 수 x까지 소수인지 합성수인지 체(배열)에다 저장하는 것입니다. 메모리와 시간만 충분하다면 선형시간에 소수인지를 판단할 수 있습니다. 먼저 예를들어 x가 10일때 를 보면 int arr[11]; for(int i=2; i

소수는 1과 자기자신을 제외하고 나누어 떨어지는 수가 없는 수입니다. 먼저 단순히 2부터 시작해서 하나씩 나누어 떨어지는지 판별하는 코드 입니다. #include int isprimeNumber(int x) { //소수 판별 (시간복잡도가 많이 듬) for (int i = 2; i < x; i++) { if (x % i == 0) return 0; //합성수 } return 1; //소수 } int main(){ int n; scanf("%d",&n); if(isprimeNumber(n)==1) printf("소수"); else printf("합성수); return 0; } 보시는 바와 같이 for문에서 i가 2부터 x-1 까지 순서대로 x와 나누어 떨어지는지 확인합니다. 물론 n이 작은 수면 상관 없지..

두 수의 최대 공약수를 구하는 방법 (유클리드 호제법)을 공부해 봤습니다. 두수 x, y 가 있을때, y가 0이 될때 까지 재귀함수로 구현해주면 됩니다. 예를들어 x가 25 y가 100이면 두수의 최대 공약수를 구하려면 사진과 같이 이루어지면 된다. 재귀 함수를 이룰 때는 y자리의 100은 x자리로 이동하고 x자리의 25는 y로 나누어 나머지가 y가 된다. 계속 재귀함수를 수행하면서 y가 0이 되었을때, x 자리의 있는 수가 최대공약수 이다. 이를 코드로 구현해보자 #include int gcd(int x, int y){ if (!y) //y==0 return x; return gcd(y, x % y); } int main(){ int a, b; scanf("%d %d",&a,&b); printf("%d..