백준알고리즘:p1978, p2581 소수찾기 소수

분류: 기본수학2

 

▶문제

p1978

 

 

▶코드

//백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 
package math_2;

import java.util.Scanner;

public class p1978 {
//소수찾기
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int count =0;
		for(int i=0; i<n; i++) {
			int num = sc.nextInt();
			boolean isPrime =true;//prime number: 소수
			if(num==1) {isPrime = false;}
			else {
				for(int k=2; k<=Math.sqrt(num); k++) {
					if(num%k==0) {isPrime=false; break;}
					else isPrime = true;
				}
			}
			if(isPrime) count+=1;
		}
		System.out.print(count);
		sc.close();
	}
}

▶소수는 1과 자기 자신의 수로만 나누어 떨어지는 숫자이다.

그래서 2부터 n까지 해당 수를 나눈 나머지가 0이 되면 소수가 아님을 알 수 있다.

그런데 만약 n이 소수인지 판별하기 위해선 n번을 확인해 봐야한다.

-> 방법1:  2~n/2 까지 나누기

-> 방법2: 2~루트n까지 나누기

n=7 일때, 1과 2의 제곱은 1, 4로 나누어 볼 가치가 있지만

3은 3^2=9 이므로 나누어 볼 가치가 없다. 그래서 루트n까지 나누는 것..

※1은 소수가 아니다. 

 

▶그래서 isPrime을 true로 두고 값이 1일때, 나머지가 0일때 false로 바꿔주기로 했다.

 소수인지 확인하는 for문은 2부터 제곱근값(내림한 정수)까지 포함해서 돌기 때문에, 

 2, 3 같이 제곱근이 2 이하인 경우엔 for문을 실행하지 않아서

선언시 isPrime=true로 두면 true값을 받을 수 있다. 

---

채점결과

 

링크 www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

 

▶문제

p2581

 

 

▶코드

//백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 
package math_2;

import java.util.ArrayList;
import java.util.Scanner;
//arrayList로 한번 구현해봤다. 소수를 구하는 방법은 p1978 방법과 같다.
public class p2581 {//소수
	//메인메소드
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M=sc.nextInt();
		int N=sc.nextInt();
		ArrayList<Integer> primeNumber = new ArrayList<>();
		
		for(int k=M; k<=N; k++) {
			if(isPrime(k)) primeNumber.add(k); 
		}
		if(!primeNumber.isEmpty()) {//소수가 존재하는 경우에만
			int mini = primeNumber.get(0);
			int sum = mini;
			for(int k=1; k<primeNumber.size(); k++) {
				sum += primeNumber.get(k);
			}
		
			System.out.print(sum+"\n"+mini);
			}
		else System.out.print(-1);
		sc.close();
		}
	//메소드
	public static boolean isPrime(int x) {
			if(x==1) return false; 
			for(int i=2; i<=Math.sqrt(x); i++) {
				if(x%i==0) return false;
			}
			return true;
	}
	
}

▶아까 문제와 같은 식으로 풀이했다. 

다만 arrayList를 사용해 봤다.

isPrime()메소드도 만들어서 사용했다. 

 

▶ArrayList는 .get(index)로 값을 얻을 수 있고, .add(value)로 리스트에 추가할 수 있다.

.isEmpty()로 리스트가 비었는지 여부를 알 수 있다.

.size()로 리스트의 크기를 알 수 있다.

 

▶메소드 만들때 주의: 메소드를 만들때 자꾸 main메소드안에 만드는 경우가 있었다.. 바보인가...

같은 클래스 안, main 메소드 밖에 만들어주기. 

main도 메소드라는 걸 까먹는 걸까....

---

채점결과

 

링크 www.acmicpc.net/problem/2581

2581번: 소수