소수

소수

@24.03.20

💡

소수 : 1과 자기 자신 외에 어떤 정수로도 나누어떨어지지 않는 정수

방법 1

• 2부터 ~ (자기 자신 - 1)까지 나누었을 때 나누어떨어지면 소수가 아니다

boolean result = true;
int number = 50;

for(int i = 2; i<number; i++){
	if(number % i == 0){ // 소수아님
		result = false; 
		break;
		}
}

방법2

• 2부터 ~ (자기 자신 - 1)까지 나눌 때 짝수는 배제하고, 나눈다.

boolean result = true;
int number = 50;

for(int i = 3; i<number; i+=2){ // 홀수로 나누기
	if(number % i == 0){ // 소수아님
		result = false; 
		break;
		}
}

방법3

• 2부터 ~ (자기 자신 - 1)까지 나눌 때 짝수는 배제한다.

• 이미 판별된 소수(2,3)로 만 나눠보고 이에 나누어떨어지면 소수가 아니다.

// 1,000 이하의 소수 나열

int count = 0; // 찾은 소수의 개수
int[] primes = new int[500]; // 소수를 저장할 배열
primes[count++] = 2; // 2는 첫 번째 소수

for (int i = 3; i <= 1000; i += 2) { // 홀수만 소수 후보로 검사
	int j;
	for (j = 1; j < count; j++) { // 이미 찾은 소수들로 나누어보기
			if (j% primes[j] == 0){ // 나누어 떨어지면 소수가 아님
					break; // 더 이상 검사할 필요 없음
			}
	}
	
	if (count== i){ // 모든 소수로 나누어떨어지지 않음
		primes[count++] = candidate; // 소수 목록에 추가
	}
}