소수(에라토스테네스 체)

2024. 4. 29. 14:48·algorithm

설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

 

입력

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

출력

첫 줄에 소수의 개수를 출력합니다.

예시 입력 1 

20

 

예시 출력 1

8

 

소스 코드 1 (시간 초과)

package section2;

import java.util.Scanner;
//시간초과걸림
public class Ex05 {
    public static int solution(int N) {
        int ans = 0;
        for (int i = 2; i <= N; i++) { //1은 소수가 아님
            for (int j = 2; j <= i; j++) { //1과 자신 이외에 나눠지는 수가 없어야 소수
                if (i % j == 0) {//if 4 ) 4,2 4,3 4,4 / 4,4만 맞아야함 근데 4,2도 나눠짐
                    if (i / j != 1) {
                        break;
                    }
                    ans++;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(solution(N));
    }
}

 

소스 코드 2

import java.util.Scanner;

public class Main {
    public static int solution(int N) {
        int ans = 0;
        int[] arr = new int[N + 1];

        for (int i = 2; i <= N; i++) {//2부터 N까지 반복
            if (arr[i] == 0) { //만약 0 이라면 카운트 해준다.
                ans++;
                
                //배수를 모두 1로 만든다. 여기서 j+=i가 아닌 j++로 검증한다면 시간초과 걸림.
                for (int j = i; j <= N; j+=i) {
                    arr[j] = 1;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(solution(N));
    }
}

'algorithm' 카테고리의 다른 글

점수계산  (0) 2024.05.06
뒤집은 소수  (0) 2024.04.29
피보나치 수열  (0) 2024.04.29
가위 바위 보  (0) 2024.04.29
보이는 학생  (0) 2024.04.29
'algorithm' 카테고리의 다른 글
  • 점수계산
  • 뒤집은 소수
  • 피보나치 수열
  • 가위 바위 보
juuuuuuun
juuuuuuun
  • juuuuuuun
    namae
    juuuuuuun
  • 전체
    오늘
    어제
    • 분류 전체보기 (94)
      • java (2)
      • Infra (4)
      • server (2)
      • algorithm (52)
      • HTTP (8)
      • android (1)
      • baekjoon (16)
      • 소프트웨어공학 (6)
      • 기타 (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
juuuuuuun
소수(에라토스테네스 체)
상단으로

티스토리툴바