간단한 문제 풀이

 

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);
	}
}