Java 数论基础：最大公约数、最小公倍数与素数

最大公约数 gcd

public static int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}

最小公倍数 lcm

public static int lcm(int a, int b) 
{
        return a / gcd(a, b)*b;
}

判断素数

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

素数筛：批量预处理

for(int i = 2;i < v.length;++i) 
		{
			if(v[i] == 0) 
			{
				list.add(i);
				for(int j = i * i;j < v.length;j+=i) 
				{
					v[j] = 1;
				}
			}
		}