[알고리즘][수학] 소수 구하기 - 에라토스테네스의 체, 소인수 분해

 

◇  코드

▷  에라토스테네스의 체

import java.util.Scanner;

public class Main_1929 {  // m 이상 n 이하인 자연수 중 소수를 모두 출력

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt(), n = sc.nextInt(), i, j;
		sc.close();

		boolean b[] = new boolean[n + 1];
		for (i = 2; (i * i) <= n; i++)
			if (!b[i])
				for (j = i * 2; j <= n; j += i)
					b[j] = true;

		StringBuilder sb = new StringBuilder();
		for (i = Math.max(2, m); i <= n; i++)
			if (!b[i])
				sb.append(i + "\n");
		System.out.println(sb.toString());
	}
}

 

▷  소인수 분해

import java.util.Scanner;

public class Main_1978 {  // n 개의 자연수 중 소수의 개수 출력

	public static boolean isPrime(int n) {
		if (n < 2) return false;
		int m = (int) Math.sqrt(n);
		for (int i = 2; i <= m; i++)
			if (n % i == 0)
				return false;
		return true;
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), a[] = new int[n], i, cnt = 0;
		for (i = 0; i < n; i++)
			a[i] = sc.nextInt();
		sc.close();
		
		for (i = 0; i < n; i++)
			if (isPrime(a[i]))
				cnt++;
		System.out.println(cnt);
	}
}