소수 판별 알고리즘 - 김희정
소수란?
1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
판별법
1.
n까지 나누어보는 방법
•
나머지(%)가 0이 아니면 소수
public boolean isPrime(int num) {
if(num==2){
return true;
}
for (int i = 2; i < num; i++) {
if (num % i == 0) { //나누어 떨어지는게 하나라도 있으면 소수 x
return false;
}
}
//다 돌았을 때 나누어떨어지는게 하나도 없었으면 소수 O
return true;
}
Java
복사
2.
n/2까지 나누어 보는 방법
public boolean isPrime(int num) {
if(num==2){
return true;
}
for (int i = 2; i < num/2; i++) {
if (num % i == 0) { //나누어 떨어지는게 하나라도 있으면 소수 x
return false;
}
}
//다 돌았을 때 나누어떨어지는게 하나도 없었으면 소수 O
return true;
}
Java
복사
3.
루트 n까지 나누어 보는 방법
public boolean isPrime(int num) {
if(num==2){
return true;
}
for (int i = 2; i*i < num; i++) {
if (num % i == 0) { //나누어 떨어지는게 하나라도 있으면 소수 x
return false;
}
}
//다 돌았을 때 나누어떨어지는게 하나도 없었으면 소수 O
return true;
}
Java
복사
TemplateCallback 패턴 적용
한가지만 바뀌고 중복일 때 주로 사용
•
템플릿 콜백 패턴은 변화되는 부분을 독립된 클래스를 만드는 것이 아니라 익명 내부 클래스를 생성하여 이를 활용
•
템플릿 : 어떤 목적을 위해 미리 만들어둔 모양이 있는 틀
•
콜백 : 호출(call)한 메소드로 다시 가는 것(back)
변화하는 부분 : 나누는 수 범위(n까지, n/2까지 ,루트 n까지 나누기)
•
getCondition(int a, int b) : 정수 두개를 받아 조건에 맞는지 아닌지 리턴
•
해당 인터페이스 구현체를 통해 내부 로직 결정
public class PrimeNum01 {
interface Compare{
boolean getCondition(int a, int b);
}
public boolean isPrime(int num, Compare compare) {
if(num==2){
return true;
}
for (int i = 2; compare.getCondition(i,num); i++) {
System.out.println(i);
if (num % i == 0) { //나누어 떨어지는게 하나라도 있으면 소수 x
return false;
}
}
//다 돌았을 때 나누어떨어지는게 하나도 없었으면 소수 O
return true;
}
public boolean isPrime01(int num){
return isPrime(num, new Compare() {
@Override
public boolean getCondition(int a, int b) {
return a<b;
}
});
}
public boolean isPrime02(int num){
return isPrime(num, new Compare() {
@Override
public boolean getCondition(int a, int b) {
return a<b/2;
}
});
}
public boolean isPrime03(int num){
return isPrime(num, new Compare() {
@Override
public boolean getCondition(int a, int b) {
return a < Math.sqrt(b)+1;
}
});
}
public static void main(String[] args) {
int[] arr = {27, 13, 17, 19, 23};
List<Integer> prime = new ArrayList<>();
PrimeNum01 primeNum01 = new PrimeNum01();
for (int elem : arr) {
if (primeNum01.isPrime03(elem)) {
prime.add(elem);
}
}
System.out.println(prime);
}
}
Java
복사
람다
•
익명 내부클래스를 람다로 대체 가능
•
장점 : 표현이 간단해서 가독성이 올라감
public boolean isPrime01(int num){
return isPrime(num, (a, b) -> a<b);
}
public boolean isPrime02(int num){
return isPrime(num, (a, b) -> a<b/2);
}
public boolean isPrime03(int num){
return isPrime(num, (a, b) -> a < Math.sqrt(b)+1);
}
Java
복사
람다 적용 전 코드
•
람다 표현식은 메서드로 전달할 수 있는 익명 함수를 단순화한 것이라고 할 수 있다.
•
람다의 특징
◦
익명 : 메서드의 이름이 없기 때문에 구현해야 할 코드에 대한 걱정거리가 줄어든다.
◦
함수 : 메서드처럼 파라미터 리스트, 바디, 반환 형식, 가능한 예외 리스트를 포함하지만 클래스에 종속되지 않으므로 함수라고 부른다.
◦
전달 : 람다표현식을 메서드 인수로 전달하거나 변수로 저장할 수 있다.
◦
간결성 : 익명 클래스처럼 클래스 이름, 메서드 이름, 파라미터 타입, 반환 타입 등이 없기 때문에 코드가 간결하다.
•
표현식 스타일(expression style) 람다(기본 문법)
(parameters) -> expression
LiveScript
복사
•
블록 스타일(block style) 람다
(parameters) -> { statements; }
LiveScript
복사
알고리즘 - 이현주 작성
오늘의 문제: [Programmers] 소수 찾기
소수 Prime Number
1. 정의 : 1보다 큰 정수 중에서 1과 자기 자신으로만 나누어지는 수
2. 소수 판별법
•
판별 대상: N
◦
방법 1 2부터 N-1까지의 수로 N을 나누어본다. 나누기 연산 결과 나머지가 0이 아닌 경우, N은 소수이다.
public boolean isPrime(int num) {
for (int i=2; **i < num**; i++) {
if ((num % i) != 0) return false;
}
return true;
}
Plain Text
복사
◦
방법 2 2부터 N/2 미만까지의 수로 N을 나누어본다. 나누기 연산 결과 나머지가 0이 아닌 경우, N은 소수이다.
public boolean isPrime(int num) {
for (int i=2; **i < num/2**; i++) {
if ((num % i) != 0) return false;
}
return true;
}
Plain Text
복사
◦
방법 3 2부터 √N 이하까지의 수로 N을 나누어본다. 나누기 연산 결과 나머지가 0이 아닌 경우, N은 소수이다.
public boolean isPrime(int num) {
for (int i=2; **i*i < num**; i++) {
if ((num % i) != 0) return false;
}
return true;
}
Plain Text
복사
▪
(참고) 반복문 조건식의 루트 표현
i * i < num 은 i < Math.sqrt(num) 과 동일한 의미이다. 단 Math 클래스가 연산이 더 많다.
3. [리팩토링] 템플릿 콜백 패턴
stage 1: 중복 기능 분리
반복문 조건식에서 중복되는 부분을 메소드로 작성한다.
boolean someOperation (int a, int b){
return a < b;
}
//방법1
boolean isPrime(int num) {
for (int i = 2; someOperation(i, num); i++) {
if (num % i == 0) return false;
}
return true;
}
//방법2
boolean isPrime2(int num) {
for (int i = 2; someOperation(i, num/2); i++) {
if (num % i == 0) return false;
}
return true;
}
//방법3
boolean isPrime3(int num) {
for (int i = 2; someOperation(i*i, num); i++) {
if (num % i == 0) return false;
}
return true;
}
Plain Text
복사
stage 2-1: StatementStrategy 적용
interface StatementStrategy {
boolean compare(int a, int b);
}
Plain Text
복사
public class TemplateCallbackPrime {
//방법1
boolean isPrime(int num, StatementStrategy stmt) {
for (int i = 2; stmt.compare(i, num); i++) {
if (num % i == 0) return false;
}
return true;
}
//방법2
boolean isPrime2(int num, StatementStrategy stmt) {
for (int i = 2; stmt.compare(i, num/2); i++) {
if (num % i == 0) return false;
}
return true;
}
//방법3
boolean isPrime3(int num, StatementStrategy stmt) {
for (int i = 2; stmt.compare(i*i, num); i++) {
if (num % i == 0) return false;
}
return true;
}
}
Plain Text
복사
stage 2-2: 익명 내부 클래스
interface StatementStrategy {
boolean compare(int a, int b);
}
Plain Text
복사
public class TemplateCallbackPrime {
//방법1
boolean isPrime(int num, StatementStrategy stmt) {
for (int i = 2; stmt.compare(i, num); i++) {
if (num % i == 0) return false;
}
return true;
}
//방법2
boolean isPrime2(int num, StatementStrategy stmt) {
for (int i = 2; stmt.compare(i, num/2); i++) {
if (num % i == 0) return false;
}
return true;
}
//방법3
boolean isPrime3(int num, StatementStrategy stmt) {
for (int i = 2; stmt.compare(i*i, num); i++) {
if (num % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
TemplateCallbackPrime tcp = new TemplateCallbackPrime();
System.out.println(tcp.isPrime(13, new StatementStrategy() {
@Override
public boolean compare(int a, int b) {
return a < b;
});
}
System.out.println(tcp.isPrime(17, new StatementStrategy() {
@Override
public boolean compare(int a, int b) {
return a < b/2;
});
}
System.out.println(tcp.isPrime(19, new StatementStrategy() {
@Override
public boolean compare(int a, int b) {
return a * a < b;
});
}
}
}
Plain Text
복사
stage 2-3: Lambda 표현식 (동작 파라미터)
Lambda란?
코드를 전달하는 과정에서 생기는 자질구레한 코드가 많은데, 람다를 통해 코드를 간결하게 전달할 수 있다. 람다를 이용하면 동작 파라미터 형식 코드를 더욱 쉽게 구현할 수 있다.
public class TemplateCallbackPrime {
//방법1
boolean isPrime(int num, StatementStrategy stmt) {
for (int i = 2; stmt.compare(i, num); i++) {
if (num % i == 0) return false;
}
return true;
}
//방법2
boolean isPrime2(int num, StatementStrategy stmt) {
for (int i = 2; stmt.compare(i, num/2); i++) {
if (num % i == 0) return false;
}
return true;
}
//방법3
boolean isPrime3(int num, StatementStrategy stmt) {
for (int i = 2; stmt.compare(i*i, num); i++) {
if (num % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
TemplateCallbackPrime tcp = new TemplateCallbackPrime();
System.out.println(tcp.isPrime(13, (a, b) -> a<b));
System.out.println(tcp.isPrime(17, (a, b) -> a<b/2));
System.out.println(tcp.isPrime(19, (a, b) -> a*a <= b));
}
}
Plain Text
복사
Lombok
Java 라이브러리로 반복되는getter,setter, 등의 메서드 작성 코드를 줄여주는 코드 다이어트 라이브러리입니다.
@AllArgsConstructor :어노테이션은 모든 필드 값을 파라미터로 받는 생성자를 만들어준다.
@NoArgsConstructor : 어노테이션은 파라미터가 없는 기본 생성자를 만들어준다
@Setter,@Getter
@Data : 위의 4가지 어노테이션이외에도 lombok어노테이션을 모두 포함하는 어노테이션이다.
@Component : 어노테이션이 달린 클래스는 Bean으로 등록해줌(@Configuration, @Bean의 역할을 하게됨)
아래 두 코드는 같은 기능
@Component
public class DaoFactory {
HospitalDao hospitalDao() {
return new HospitalDao(new JdbcTemplate());
}
}
Java
복사
@Configuration
public class DaoFactory {
@Bean
HospitalDao hospitalDao() {
return new HospitalDao(new JdbcTemplate());
}
}
Java
복사
@SpringBootApplication
@SpringBootApplicaion은 세가지 어노테이션의 역할을 수행
•
@EnableAutoConfiguration
•
@ComponentScan
•
@SpringBootConfiguration
@ComponentScan
@SpringBootApplication 이 붙은 클래스 이하에 있는 모든 패키지를 스캔해서 @Component가 붙어 있거나 @Configuration, @Service, @Repository 등이 붙어있는 클래스를 빈으로 등록함
@SpringBootConfiguration
스프링부트의 설정을 나타냄 (스프링의 @Configuration 대체)
@EnableAutoConfiguration
클래스 경로에 미리 정의된 라이브러리들을 Bean으로 등록
@SpringBootTest : @SpringBootApplication와 다른 디렉토리에 있기 때문에 Test시 꼭 붙여줘야함
@Autowired
•
ApplicationContext = Spring 에 등록된 빈을 '이름'에 맞게 DI를 해줌
•
@Autowired 어노테이션이 ApplicationContext에서 Bean을 찾아 주입해주는 형식
queryForObject()
•
SELECT를 실행했을 때 하나의 객체(Object) 결과 값이 나올 때 사용하는 메소드
