소수 구하기 - 기본
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | package AD; import java.util.*; public class test { public static void main(String[] args) { int count =0; for(int n = 2;n<=1000;n++) { int i; for(i=2;i<n;i++) { count++; if(n%i==0) break; } if(n==i) System.out.println(n); } System.out.print("비교연산횟수:"+count); } } | cs |
알고리즘 개선(1) - 에라토스테네스의 체. 숫자는 소수의 곱으로 이루어져 있기 때문에 찾은 소수를 저장해, 대상과 비교한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | package AD; import java.util.*; public class test { public static void main(String[] args) { int count = 0; int pn = 1; // 찾은 소수의 개수 int[] prime = new int[1000]; prime[0]=2; for(int n = 3;n<=1000;n+=2) { //판단대상 int i; for(i=1;pn>i;i++) { count++; if(n%prime[i]==0) break; } if(pn==i) prime[pn++]=n; } for(int i=0;pn>i;i++) System.out.println(prime[i]); System.out.print("비교연산횟수:"+count); } } | cs |
알고리즘 개선(2) - 제곱근 n까지 나누어지는 소수가 없으면 소수.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | package AD; import java.util.*; public class test { public static void main(String[] args) { int count = 0; int pn = 2; // 찾은 소수의 개수 int[] prime = new int[500]; prime[1]=3; prime[0]=2; for(int n = 5;n<=1000;n+=2) { //판단대상 boolean flag = false; for(int i=1;prime[i]*prime[i]<=n;i++) { //n의 제곱근까지 나눠지는 소수가 없는 지 판단 count+=2; if(n%prime[i]==0) { flag = true; break; } } if(!flag) { count++; prime[pn++]=n; } } for(int i=0;pn>i;i++) System.out.println(prime[i]); System.out.print("곱셈,나눗셈 연산횟수:"+count); } } | cs |
