[C#, JAVA] n이하의 소수 리스트

소수는 알고리즘 문제의 단골 손님인데, 보통 시간 초과에 막히는 문제가 많다. 따라서 소수 판별 시간을 줄이는 것이 일순위인데 아래 코드에선 소수의 두 가지 성질을 이용했다.

 

1. 어떤 수를 그 수의 제곱근보다 작은 소수들로 나눴을 때 나누어 떨어지지 않는다면 그 수는 소수이다.

2. 2를 제외한 모든 짝수는 소수가 아니다.

 

더 빠른 방법을 찾을 시 수정

 

using System;
using System.Collections.Generic;

class Program   //사용 예
{
    static void Main(string[] args)
    {
        Prime p = new Prime();
        p.makePrime(100);
        List<long> list = p.getList;
        foreach (long l in list)
            Console.WriteLine(l);
    }
}
class Prime
{
    private List<long> primeList;
    public Prime()
    {
        primeList = new List<long>();
    }
    public Prime(int n)
    {
        primeList = new List<long>();
        makePrime(n);
    }
    public List<long> getList { get { return primeList; } }
    public void makePrime(long n)
    {
        long tmp = 3;
        long tmpRoute;
        bool flag;
        primeList.Add(2);   //처음에 2추가
        while (tmp <= n)
        {
            flag = true;
            tmpRoute = (int)Math.Sqrt(tmp); //주어진 수의 제곱근
            foreach (long l in primeList)   //제곱근보다 작은 소수로만 판별
            {
                if (l > tmpRoute)   
                    break;
                if (tmp % l == 0)   
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
                primeList.Add(tmp);
            tmp += 2;      //2씩 증가하면서 판별
        }
    }
    public void clear()
    {
        primeList.Clear();
    }
}

 

2023.07.30 JAVA 버전 추가

 

class Prime{
	List<Integer> prime;
	
	List<Integer> getPrimeList(int max){
		prime = new ArrayList<Integer>();
		boolean flag;
		int tmp = 3;
		prime.add(2);
		while (tmp <= max) {
			flag = true;
			int tmpRoute = (int) Math.sqrt(tmp);
			for (int p : prime) {
				if (p > tmpRoute)
					break;
				if (tmp % p == 0) {
					flag = false;
					break;
				}
			}
			if (flag) {
				prime.add(tmp);
			}
			tmp += 2;
		}
		return prime;
	}
}