소수 찾기 알고리즘

소수 찾기 알고리즘

 

우선 소수란?

내가 알기로는 1을 제외한 자기 자신만을 약수로 가지는 수이다.

 

두산백과에서는

1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수

 

그래서 무식하게 우선 생각을 해봤다.

 

내가 구현할건 입력 받은 숫자 아래의 모든 소수 찾기이다.

 

입력받은 숫자아래의 모든 양의 정수를

2부터 시작하여 다 나눠서 나누어 떨어지는 숫자의 카운트를 체크하여 출력하는 방식이다.

 

이중 포문을 이용하여 입력받은 숫자이하의 모든 숫자에 대하여 2부터 자기 자신까지 나눠서 카운트가 1인 숫자만 출력하게 된다.

 

좀더 간단한 알고리즘을 찾아봐야겠다.

 

아래는 예제소스

package practice;
 
public class FindPrime {
 
public void findPrime(int num)
{
 
 for(int i =2; i<=num; i++)
 {
  int cnt =0;
  for(int j=2; j<=i; j++)
  {
  if(i%j == 0)
  {
   cnt +=1;
  }
 
  }
  if(cnt == 1)
   System.out.println(i);
 }
 
}
public static void main(String[] args) {
 int num =40;
 
 FindPrime fp = new FindPrime();
 fp.findPrime(num);
}
}