Doit자바 알고리즘 - 1
업데이트:
소수의 나열
package com.practiceExample.Doit;
public class PrimeNumber {
public static void main(String[] args) {
int counter = 0;
for(int n = 2; n <= 1000; n++) {
int i;
for(i = 2; i < n; i++) {
counter++;
if(n % i == 0)
break;
}
if(n == i) {
System.out.println(n);
}
}
System.out.println(counter);
}
}
소수를 구하는 과정
package com.practiceExample.Doit.chap02;
public class PrimNumber2 {
public static void main(String[] args) {
int counter = 0; // 나눗셈 횟수
int ptr = 0; // 찾은 소수의 갯수
int[] prime = new int[500]; // 소수를 저장하는 배열
prime[ptr++] = 2; // 2는 소수다.
for(int i = 3; i <= 1000; i+=2) { // 대상은 홀수만
int j;
for(j = 1; j < ptr; j++) { // 이미 찾은 소수로 나누기
counter++;
if(i % prime[j] == 0) { // 나머지가 0이면 짝수
break;
}
}
if(ptr == j) { // 마지막까지 나누어 떨어지지 않는것
prime[ptr++] = i; // 배열에 저장한다,
}
}
for(int i = 0; i < ptr; i++) {
System.out.println(prime[i]);
}
System.out.println(counter);
}
}
소수의 조건
n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.
프로그램에서 곱셈의 처리비용은 나눗셈과 같다.
소수 구하기 - part3
package com.practiceExample.Doit.chap02;
public class PrimeNumber3 {
public static void main(String[] args) {
int counter = 0;
int ptr = 0;
int[] prime = new int[500];
prime[ptr++] = 2;
prime[ptr++] = 3;
for(int i = 5; i <= 1000; i += 2) {
boolean flag = false;
for(int j = 1; prime[j] * prime[j] <= i; j++) {
counter += 2;
if(i % prime[j] == 0) {
flag = true;
break;
}
}
if(!flag) {
prime[ptr++] = i;
counter++;
}
}
for(int i = 0; i < ptr; i++) {
System.out.println(prime[i]);
}
System.out.println("수행횟수 : "+ counter);
}
}
안쪽의 for문을 반복할 때 마다 counter를 2씩 증가시키는 것은 다음 두 연산의 수행 횟수를 계산하기 위함이다.
곱셈 : ...prime[i] * prime[i]
나눗셈 ... : n % prime[i]
prime[i] * prime[i] <= 이 성립하지 않는 경우 프로그램 흐름이 안쪽 for문의 루프 본문으로 들어가지 않으므로 그 곱셈이 수행횟수에 포함되지 않는다. 그래서 for문 종료후
if(!flag) {
prime[ptr++] = i;
counter++;
}
이 if문에서 그 부분을 횟수에 포함시킨다.
댓글남기기