Fermat 소인수분해 코딩소스

소개

Fermat 방식으로 소인수분해를 하는 프로그램 소스입니다
다음과같은 알고리즘으로 소인수분해를 한다
1.n의 제곱근을 구하여 정수이면 끝내고, 아니면 t를 n의 제곱근보다 큰수들 중에 가장 작은 정수라 놓는다.
2. z = t^2 - n
3. z가 완전제곱수 s^2이면 n = t^2 - s^2 이므로 끝내고 아니면 다음순서로 간다.
4. t= t+1 로 놓고 순서 2로 돌아간다.

컴파일 실행환경

없음

본문내용

#include <stdio.h>
#include <math.h> // 함수 sqrt, modf를 사용하기 위한 헤더파일.
int main()
{
int n,t,z;
double s, rootn, ipart;

printf(" 정수 n을 입력해 주세요. nn");

scanf("%d", &n);
printf(" n = %d 이면", n);


rootn = sqrt(n); // 루트n을 구하는 함수. rootn은 n의 제곱근을

의미하는 변수.
printf(" n의 제곱근은 %f 입니다.nn" ,rootn);


if (modf(rootn, & ipart)==0.0){ // 정수인지 아닌지를 판별하는 함수
printf(" n의 제곱근이 정수 이면nn");
printf(" %d = %.0f * %.0f 입니다nn", n , rootn, rootn);
}
.....................

참고자료

· 없음