(알고리즘) 소수 판별, 소인수 분해, 에라스토테네스 알고리즘

1. 시간복잡도가 O(루트n)시간에 동작하는 소수 판별 알고리즘

--->합성수 n이 p*q로 표현 될 때 한 수는 항상  루트n이하,  다른 한 수는 루트n이상이 된다.

public class isPrime {

boolean isPrime(int n)
{
if(n<=1)return false;
if(n==2)return true;

if(n%2==0)return false;

int sqrtn=(int)Math.sqrt(n);

for(int div=3;div<=sqrtn;div+=3)
{
if(n%div==0)
return false;
}
return true;
}
}


2. 소인수 분해 O(루트n)

private static Vector<Integer> factorSimple(int n)
{
Vector<Integer> ret=new Vector();
int sqrtn=(int)Math.sqrt(n);

for(int div=2;div<=sqrtn;div++)
{
while(n%div==0)
{
n/=div;
ret.add(div);
}
}
if(n>1)ret.add(n);
return ret;
}


3. 에라스토테네스(시간복잡도는 O(nloglogn)이다 이것은 O(n)이랑 비슷)
public class erastotenes {

private static int MAX_N;
private static boolean isPrime[]=new boolean[MAX_N];

private static void erastotenes(int n)
{
Arrays.fill(isPrime,true);
isPrime[0]=isPrime[1]=false;
int sqrtn=(int)Math.sqrt(n);

for(int div=2;div<=sqrtn;div++)
{
if(isPrime[div])
   for(int j=div*div;j<=sqrtn;j+=div)
   {
    isPrime[j]=false;
   }
}

}

}