Programming/Java
간단한 문제 풀이
mj73
2021. 6. 30. 17:49
1. 1부터 입력 받은 수 사이에 있는 모든 소수들을 출력하는 프로그램
배경지식:
-입력 받은 수를 n이라고 하자.
-1은 소수가 아니다.
-2부터 n-1까지로 나눴을때 하나라도 나누어 떨어지는 수가 있다면 소수가 아니다.
-n의 약수가 n/2보다 클 수 없기 때문에 2부터 n/2 사이의 정수로 나누어 떨어지는지 확인하는 것이 낫다.
-2부터 n/2까지의 정수보다 2부터 루트n까지의 정수로 나누어 떨어지는지 확인하는 것이 더 낫다.
따라서 for(int j=2; j<sqrt(n); j++); 로 나타낼 수 있는데,
이는 for(int j=2; j*j<n; j++); 이라고도 쓸 수 있다.
import java.util.Scanner;
public class Example03 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for(int i=2; i<=n; i++) {
boolean isPrime = true;
for(int j=2; j*j<=i && isPrime; j++)
if(i%j == 0)
isPrime = false;
if(isPrime)
System.out.println(i);
}
}
}
2. n개의 정수를 입력받아 배열에 저장하고,
0개 이상의 연속된 정수들을 더하여 얻을 수 있는 최대값을 구하고 출력하는 프로그램
-n개의 정수로 만들 수 있는 모든 구간들을 검사하고 각 구간의 합을 구한다.
-i는 출발점, j는 i부터 끝까지 이동한다.
import java.util.Scanner;
public class Example04 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int [] data = new int[n];
for(int i=0; i<n; i++)
data[i] = scanner.nextInt();
scanner.close();
int max=0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
int sum = 0;
for(int k=i; k<=j; k++)
sum += data[k];
if(sum > max)
max= sum;
}
}
System.out.println("max: "+max);
}
}
다른 방법:
import java.util.Scanner;
public class Example04 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int [] data = new int[n];
for(int i=0; i<n; i++)
data[i] = scanner.nextInt();
scanner.close();
int max=0;
for(int i=0; i<n; i++) {
int sum = 0; //i가 바뀔 때마다 sum을 0으로 초기화
for(int j=i; j<n; j++) {
sum += data[j];
if(sum > max)
max= sum;
}
}
System.out.println("max: "+max);
}
}