오늘은 최대공약수와 , 최소공배수 , 소수를 알아보고 문제를 풀어봤다.
최대공약수 : 약수중 가장큰수 , ex) 6 , 12 일떄 6은 1,2,3,6이 약수 , 12는 1,2,3,4,6,12 가 약수이떄 이때 가장 큰 약수 6이 최대 공약수가 된다
최소공배수 : 배수중 공통되는 배수가 가장 작은값 ex) 4, 6 일때 4의 배수 4,8,12,16,20,24 , 6의배수 6,12,18,24.. 첫번째 겹치는 12가 최소 공배수이다
소수 : 약수중 몫이 1과 자기자신이 되는 수 ex) 2 ,3 ,5 7, 11, 13 ,17 ,19 ,23 ....
1. N번째 큰 수
입력받은 값은 배열에 담고 Arrays.sort를 사용하여 전체 길이 - N번째 = 작은수를 찾았다 ( 큰수를 찾으려면 reverse를 사용해야한다 )
https://www.acmicpc.net/problem/2693
2693번: N번째 큰 수
첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000보
www.acmicpc.net
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
int n = Integer.parseInt(input);
for(int i =0 ; i <n ;i++) {
String str = sc.nextLine();
int[] arr = new int[10];
for(int j = 0 ; j<arr.length;j++) {
arr[j]=Integer.parseInt(str.split(" ")[j]);
}
Arrays.sort(arr);
System.out.println(arr[7]);
}
}
}
2. 소수찾기
주어진 값중에 소수가 몇개인지를찾는 문제이다.
주의사항은 0과 1을 소수에서 제외해야하고 , 값 N이 소수인지 찾을때 2부터 n까지 나눗셈을 하여 나머지가 0인 경우가 아닌경우만 소수로 판단한다.
https://www.acmicpc.net/problem/1978
1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
int n = Integer.parseInt(input);
String str = sc.nextLine();
int count = 0;
for(int i =0 ; i < n ;i++) {
boolean b = false;
int[] arr = new int[n];
for(int j = 0 ; j<arr.length;j++) {
arr[j]=Integer.parseInt(str.split(" ")[j]);
}
if(arr[i]==0) {
b=true;
}
if(arr[i]==1) {
b=true;
}
for(int j = 2;j<arr[i];j++) {
if(arr[i]%j==0) {
b=true;
}
}
if(!b) count++;
}
System.out.println(count);
}
}
3. 최대공약수와 최소공배수
입력값 n과 m 둘다 만족하는 약수를 찾고 찾을때마다 해당 약수를 기억한다.
마지막에 남은 약수가 최대공약수가 되고
n*m/ 최대공약수를 하면 최소 공배수를 구할수 있다.
https://www.acmicpc.net/problem/2609
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
int n = Integer.parseInt(input.split(" ")[0]);
int m = Integer.parseInt(input.split(" ")[1]);
int L = 0 ; //최대공약수
for( int i=1 ; i<=n && i <=m ; i++) {
if ( n%i==0&& m%i==0) {
L=i;
}
}
int O = n*m/L;
System.out.println(L);
System.out.println(O);
}
}
4. 지정된 범위내의 소수를 찾아 더하고 , 가장작은 소수를 뽑아라
소수찾기 알고리즘 공부하면서 소수의 배수는 소수가 아니라는것을 적용한 문제이다
수가 크다는 가정을하고 위에 소수찾기와 다르게 진행하였다
ex) 주어진수가 2~120이라고하면 , 2부터 120까지 하나씩 소수인지를 검사할 예정이다
첫번째 2는 소수이다. 그리고 2를 제외한 ,4,6,8,10....120) 은 소수가 아님으로 소수검사를 할필요가없다
3의 배수 3을제외한 ,6,9,12....120) 또한 소수가 아님으로 검사할 필요가없다. 이렇게되면 양이 확 줄어든다.
이 방식을 사용하기위해 boolean 배열을 사용하였다.
https://www.acmicpc.net/problem/2581
2581번: 소수
M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.
www.acmicpc.net
package com.myproject.CodeTest;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.nextLine();
int m = Integer.parseInt(a);
String b = sc.nextLine();
int n = Integer.parseInt(b);
boolean[] arr = new boolean[n+1];
ArrayList<Integer> list =new ArrayList<Integer>();
int total=0;
for( int i = m ; i <= n ; i++) {
arr[0]=true; //소수는 2부터 생기때문
arr[1]=true; //소수는 2부터 생기때문
if(!arr[i]) { //이미 소수가 아닌애들은 계산하지 않는다
for(int j=2;j<=Math.sqrt(i);j++) { //루트i 이기때문에 밑에 조건이 소수가 된다.
if(i%j==0) { //소수가 아닌경우
arr[i]=true; //해당 수를 true로 변경
int k = i/j; //해당 수 부터 종료 숫자까지 해당수의 곱셈은 다 소수가 아니다
for ( int l = 1; l <=k ; l++) {
arr[l*j]=true;
}
}
}
}
if(arr[i]==false) {
total+=i;
list.add(i);
}
}
if(list.size()==0) {
System.out.println(-1);
}else {
System.out.println(total);
System.out.println(list.get(0));
}
}
}
