[java] 문제 037 (백준 1929)

문제

수들의 합 5

 

교재 풀이

import java.util.Scanner;
public class P1929_소수구하기 {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int M = in.nextInt();
    int N = in.nextInt();
    int[] A = new int[N + 1];
    for (int i = 2; i <= N; i++) {
      A[i] = i;
    }
    for (int i = 2; i <= Math.sqrt(N); i++) { // 제곱근 까지만 수행
      if (A[i] == 0) {
        continue;
      }
      for (int j = i + i; j <= N; j = j + i) { // 배수 지우기
        A[j] = 0;
      }
    }
    for (int i = M; i <= N; i++) {
      if (A[i] != 0) {
        System.out.println(A[(int) i]);
      }
    }
  }
}

 

내 풀이) 24.6.19에 풀고 아깝게 틀림

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) throws IOException{
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        
        int[] nums=new int[n+1];
        for(int i=0;i<=n;i++){
            nums[i]=i;
        }
        
        for(int i=2;i<=Math.sqrt(n);i++){
            if(nums[i]==0)
                continue;
            
            for(int j=i+i;j<=n;j+=i){
                nums[j]=0;
            }
        }
        
        for(int i=m;i<=n;i++){
            if(nums[i]!=0)
                System.out.println(nums[i]);
        }
        
	}
}



//첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. 
//    (1 ≤ M ≤ N ≤ 1,000,000)
//M이상 N이하의 소수를 모두 출력
//    한 줄에 하나씩, 증가하는 순서대로 소수를 출력
//
//입력
//3 16
//출력
//3
//5
//7
//11
//13
//
//접근법
//    에라토스테네스의 체를 구현하면 되는 문제
//        일단 범위만큼 숫자 배열을 만들고 (즉 for문으로 숫자 배열을 i로 넣어주고)
//        그 배열을 가지고 for문을 돌면서 소수의 배수를 계속 삭제
//        일단 체 구현은 이중 for문이고 
//    그렇게 에라토스테네스 체로 거른 소수만 남은 배열이 생성되면
//        그것만 출력하면 됨. 
//        출력할 거 안 할거 구분은 배열의 값으로 하면 됨
//            그러니까 소수가 아닌 거는 0으로 일괄적으로 업데이트해서 
//            0이 아닌 것만 출력하는 거지. 조건문으로
//슈도코드 
//    m,n을 입력받음
//        sc로 하면 되고 
//    
//    숫자 배열을 만들기 
//        크기는 어떻게? n-m+1
//            즉 16-3+1은 14고
//            배열 인덱스 시작을 1로 하기 위해서 +1를 해줌?
//            아니다. 3 이상 16이하니까 이 땐 +1로 해주는 게 맞음
//            아님, 크기를 17로 하고 
//        for문 이용해서
//            각 숫자 배열의 값은 i로 입력되게 하기
//            이 때 i 시작은 m, n이하일 때까지 반복하기
//    
//    for문 돌면서 소수의 배수를 계속 삭제 
//        어떻게? 
//            처음에 2부터 시작해 
//            for j=i+i;j<=n;j+=i => 이게 내부 반복문임
//            내부 반복문 안에서 해당되는 인덱스의 값을 0으로 바꾸기 
//    
//    for 숫자 배열 크기만큼 반복하면서
//        if a[i]가 0이라면 continue
//        아니면 println a[i]

 

내 풀이2) 24.6.19에 풀고 아깝게 틀린 걸 => chatGpt가 코드 몇 줄 넣어서 고쳐줌

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        
        int[] nums = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            nums[i] = i;
        }

        nums[0] = 0; // 0은 소수가 아님
        nums[1] = 0; // 1은 소수가 아님

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (nums[i] != 0) {
                for (int j = i * i; j <= n; j += i) { // j = i * i부터 시작
                    nums[j] = 0;
                }
            }
        }

        for (int i = m; i <= n; i++) {
            if (nums[i] != 0) {
                System.out.println(nums[i]);
            }
        }
    }
}

 

설명

내 풀이2는 다음이 달라짐

 

• 0과 1을 소수가 아닌 것으로 초기화:이는 0과 1을 소수로 처리하지 않기 위해 초기값을 설정한 것입니다.
  • nums[0] = 0; // 0은 소수가 아님
  • nums[1] = 0; // 1은 소수가 아님
• 내부 루프에서 시작 인덱스 수정:이는 내부 루프의 시작 인덱스를 j = i * i로 설정합니다. j = i * i부터 시작하면, 이미 처리된 값들을 다시 처리하지 않게 됩니다. 이는 에라토스테네스의 체의 효율성을 높입니다.
  • for (int j = i * i; j <= n; j += i) {