코딩 07. 소수 구하기
소수란 ? 1과 자신으로만 나누어지는 수
int n = 100; boolean boo; for(int i = 2; i < n; i++) { // 1은 소수가 아니기 때문에 제외 boo = true; for(int j = 2; j <= i/2; j++) { if(i%j == 0) { boo = false; break; } } if (boo == true) System.out.printf("%3d", i); }
자연수 i를 2로 나눈 이유는,
예를 들어 자연수 8을 소인수분해하면 1, 2, 4, 8이 나오는데 1과 8이 짝꿍이고, 2와 4가 짝꿍이기 때문에 1, 2 이후에 나오는 4, 8은 신경쓸 필요가 없어진다.
:-D ? 에라토스테네스의 체
int n = 15; int arr[] = new int[n]; for (int i = 0; i < n; i++) { arr[i] = i + 1; } for (int i = 2; i <= n; i++) { if (arr[i - 1] == 0) continue; int j = 2; while ((i * j) - 1 < n) { arr[(i * j) - 1] = 0; j++; } }
2부터 시작해서 2의 배수를 지운다.
다음은 3의 배수를 지운다.
4의 배수는 2의 배수이기 때문에 지워져있다.
5의 배수를 지운다.
6은 2, 3의 배수이기 때문에 지워져있다.
.
.
.
이런식으로 가면 2, 3, 5, 7, 11 ... 이 나온다.
Author And Source
이 문제에 관하여(코딩 07. 소수 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yuriyaam/코딩-07.-소수-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)