소인수분해 하는 소스 코드 작성해봤는데요.

kknd345의 이미지

#include<stdio.h>

void getPrime(int FirstInputNumber)/*소인수 구하는 함수입니다*/
{
		int i,PrimeNumber,InputNumber;
		int Prime[50];
		int X;
		PrimeNumber=0;
		InputNumber=FirstInputNumber;
		X=1;

		for(i=2;i<InputNumber;i++)
		{
			if(InputNumber%i==0)
			{
				Prime[PrimeNumber]=i;
				PrimeNumber++;
				InputNumber=InputNumber/i;
				i=2;
			}
		}

		if(FirstInputNumber==InputNumber) // 소수는 그 자체가 소인수이다. 
		{								  // for식에 해당 사항이 없어서 따로 지정
			X=FirstInputNumber;
		}

		i=0;
		
		while(FirstInputNumber!=X)
		{
			printf("%d ",Prime[i]);
				X=X*Prime[i];
			i++;
		}
}

void main()
{
	int wanted;
	printf("소인수분해하고 싶은 수를 입력하시오\n");
	scanf("%d",&wanted);

	getPrime(wanted);
}

실행해보니 앞에 한개만 맞고 그 다음에 이상한 숫자 -15910580 같은걸 출력하네요. 에러 메시지가 뜨네요.

배열에 값을 넣을때 저런 식으로 넣으면 안되나요??
포인터를 꼭 사용해야 하나요?
그리고 맞게 고치면 어떤식으로 되는지좀 가르쳐주세요.

댓글

sliver의 이미지

#include<stdio.h> 

void getPrime(int FirstInputNumber)
{ 
      int i,PrimeNumber,InputNumber; 
      int Prime[50]; 
      int X; 
      PrimeNumber=0; 
      InputNumber=FirstInputNumber; 

      for(i=2;i<InputNumber;i++) 
      { 
         if(InputNumber%i==0) 
         { 
            Prime[PrimeNumber]=i; 
            PrimeNumber++; 
            InputNumber=InputNumber/i; 
            i=1;  // <- i++가 수행될테니 i=1로 해야합니다..
         } 
      } 

      X=InputNumber; // <- 경우에 상관없이 InputNumber로 해야합니다..

      i=0; 
       
      while(FirstInputNumber!=X) 
      { 
         printf("%d ",Prime[i]); 
         X=X*Prime[i]; 
         i++; 
      }
      printf("%d\n",InputNumber); // <- 처음의 루프가 끝나면 InputNumber도 원래 FirstInputNumber의 수인수일테니 이것도 출력해야죠..
} 

void main() 
{ 
   int wanted; 
   printf("소인수분해하고 싶은 수를 입력하시오\n"); 
   scanf("%d",&wanted); 

   getPrime(wanted); 
}
ㅡ,.ㅡ;;의 이미지

변수명너무길어 변수명읽다 지쳤다..ㅡ,.ㅡ;;

옛날에.. 김수한무삼천각자동방석..... 이물에 빠졌는데..어쩌고 하는이야기가 생각나는...


----------------------------------------------------------------------------

xyhan의 이미지

예전프로젝트에서는 for문에 사용하는 index도 i를 쓰지 말라고 금했는데...
물런 i,j,k, x,y,z, a,b,c 로 도배하던 시절도 있었는데..

============================================================

선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-

============================================================

============================================================

선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-

============================================================

익명 사용자의 이미지

김 수한무 삼천갑자 동방 삵 이에요ㅎ 장수하는생물들 쭉 나열하는거

sangwoo의 이미지

음.. 소인수분해는 분해하고자 하는 수의 sqrt() 보다 작은 2이상의 정수로 모두
나누어보아야 하는 거 아닌가요?

----
Let's shut up and code.

kknd345의 이미지

#include<stdio.h>

void getPrime(int FirstInputNumber)/*소인수 구하는 함수입니다*/
{
		int i,PrimeNumber,InputNumber;
		int Prime[50];/*소인수가 50개가 넘으면 []안의 숫자를 알맞게 올려주심 됩니다*/
		int X;
		PrimeNumber=0;
		InputNumber=FirstInputNumber;
	

		for(i=2;i<=InputNumber;i++)
		{
			if(InputNumber%i==0)
			{
				Prime[PrimeNumber]=i;
				PrimeNumber++;
				InputNumber=InputNumber/i;
				i=1;
			}
		}
X=1;

		i=0;
		
		while(FirstInputNumber!=X)
		{
			printf("%d ",Prime[i]);
				X=X*Prime[i];
			i++;
		}
}

void main()
{
	int wanted;
	printf("소인수분해하고 싶은 수를 입력하시오\n");
	scanf("%d",&wanted);

	getPrime(wanted);
}

완성 코드 예요

X=1; 이나 X=InputNumber; 나 똑같더군요.

그리고
for(i=2;i<=InputNumber;i++) 에서 =를 추가시켰습니다.

그러니 마지막 소인수가 빠지는 오류 없이 잘 되네요 .

그리고 소인수는 2이상의 수로 나누어 떨어지는게 있으면 그 뒤는 몫만 가지고 또 나누고 그런식으로 하면 소인수를 다 구할수 있죠 ^^

1%의 가능성이면 충분하다!
최선을 다하자!

litdream의 이미지

int getPrime(int FirstInputNumber, int arr[]) ;

어짜피 출력만 하고 끝나면 재미없으니깐,
답을 저장할 배열을 넘겨주고(배열의 크기는 부르는쪽에서 알아서 결정하기로 하고),
몇개의 prime number 가 나왔는지를 넘겨주면 훨씬 유용한 함수가 되지 않을까 생각합니다.

초보의 의견이었슴다.

삽질의 대마왕...

sangwoo의 이미지

sangwoo wrote:
음.. 소인수분해는 분해하고자 하는 수의 sqrt() 보다 작은 2이상의 정수로 모두
나누어보아야 하는 거 아닌가요?

약수 구하는 거랑 헷갈렸습니다.. :oops:
덧. 심심해서 저도 한번 짜봤습니다.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long
lpdof(long long target)
{
        long long i, ret;

        ret = target;
        for (i = 2; i <= (long long)sqrt((double)target); i++)
                if (target % i == 0) {
                        ret = i;
                        break;
                }
        return (ret);
}

void
usage(const char *name)
{
        fprintf(stderr, "Usage: %s <number>\n", name);
        exit(1);
}

int
main(int argc, char *argv[])
{
        long long target, lpd;

        if (argc != 2 || (target = strtoll(argv[1], NULL, 10)) <= 0)
                usage(argv[0]);
        for (;;) {
                lpd = lpdof(target);
                printf("%lld ", lpd);
                if (lpd == target)
                        break;
                target /= lpd;
        }
        printf("\n");
        return (0);
}

출력만 하는 거라.. 배열에 넣거나 하진 않았습니다.

----
Let's shut up and code.

cedar의 이미지

2로 나누어 떨어지지 않을 때까지 나눈 후,
3부터 제곱근까지의 홀수로 나누어 가는 방식을 사용했습니다.
(속도가 약간 향상되지요.)

litdream wrote:
int getPrime(int FirstInputNumber, int arr[]) ;

어짜피 출력만 하고 끝나면 재미없으니깐,
답을 저장할 배열을 넘겨주고(배열의 크기는 부르는쪽에서 알아서 결정하기로 하고),
몇개의 prime number 가 나왔는지를 넘겨주면 훨씬 유용한 함수가 되지 않을까 생각합니다.

초보의 의견이었슴다.

고정되어 있지 않은 여러개의 리턴값을 갖는 함수의 디자인은
다음과 같이 출력 반복자를 사용하면 간편합니다.

#include <iostream>
#include <iterator>

template <typename IntegerType, typename OutputIterator>
void prime_factor(IntegerType m, OutputIterator result)
{
    while (m % 2 == 0) {
        m /= 2;
        *result++ = 2;
    }
    if (m > 1) {
        for (IntegerType d = 3; m >= d * d; d += 2)
            while ((m % d) == 0) {
                m /= d;
                *result++ = d;
        }
        if (m > 1) *result++ = m;
    }
}

int main()
{
    int m;
    while (std::cin >> m) {
        prime_factor(m, std::ostream_iterator<int>(std::cout, " "));
        std::cout.put('\n');
    }
    return 0;
}
차리서의 이미지

primes = sieve [2..] where sieve (x:xs) = x : sieve [ n | n <- xs, rem n x /= 0 ]

factorize n = factorize' n primes where
    factorize' n (p:ps)
        | n < p        = []
        | rem n p == 0 = p : factorize' (quot n p) (p:ps)
        | otherwise    = factorize' n ps

--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!

서지원의 이미지

(defun factorize (n)
  (labels ((factor-aux (try num)
             (cond ((= try num)  (list try))
                   ((zerop (mod num try))
                    (nconc (list try) (factor-aux try (/ num try))))
                   (t (factor-aux (1+ try) num)))))
    (factor-aux 2 n)))

CL-USER 55 > (factorize 20)
(2 2 5)

(defun get-divisors (n)
  (loop for i from 2 to n
           when (zerop (mod n i)) collect i))

CL-USER 18 > (get-divisors 20)
(2 4 5 10 20)

하나는 약수를 구하는 함수이고, 다른 하나는 소인수분해 하는 함수입니다.[/code]
magingax의 이미지

저도 LISP 사용자인데..반갑습니다..^^

LISP 사용자모임
http://cafe.naver.com/lisper
방송기술 개발업체
http://playhouseinc.co.kr

cdpark의 이미지

http://groups.google.co.kr/groups?threadm=3F137DB7.5B957270%40bawi.org

구글에는 일부만 있군요. 이 쓰레드로 유즈넷에 있는 글은 대략 40개 쯤인데..

natas999의 이미지

2부터 끝까지 나누려니까 엄청 오래 걸리네요.

$ time ./factor 313418913
3 104472971

real    0m15.170s
user    0m5.550s
sys     0m0.030s
$ time factor 313418913
313418913: 3 104472971

real    0m0.041s
user    0m0.000s
sys     0m0.020s

정수 범위 내의 소수를 셋으로 가지고 있다가 참조하면 가장 빠르겠죠?
그 다음 빠른 방법은 뭐가 있을까요?

# emerge girl-friend
Calculating dependencies
!!! All wemen who could satisfy "girl-friend" have been masked.

natas999의 이미지

2하고 홀수로만 하니까 훨씬 빨라지네요.

 $ time factor 313418913
313418913: 3 104472971

real    0m0.010s
user    0m0.000s
sys     0m0.010s
 $ time ./factor 313418913
313418913: 3 104472971

real    0m1.794s
user    0m1.750s
sys     0m0.010s

하지만 여전히 GNU factor와 비교해서 엄청나게 느린속도.

# emerge girl-friend
Calculating dependencies
!!! All wemen who could satisfy "girl-friend" have been masked.

chaeso의 이미지

뭐 그럭저럭 쓸만한 테크닉으로 페르마 인수분해가 있습니다

만약~ 6077 을 인수분해 하려면

sqrt(6077) 보다 큰 정수 78 을 고르구요..

78^2 - 6077 = 7 = 무리수 ^2
79^2 - 6077 = 164 = 무리수 ^2
80^2 - 6077 = 323 = 무리수 ^2
81^2 - 6077 = 484 = 22^2 = 정수 ^2

이렇게 되면...
81^2 - 22^2 = 6077 로 옮기구요
(81 + 22)(81 - 22) = 6077 로 바꾸고
103 * 59 = 6077 ..
6077 은 103 과 59 의 곱이니까 103 도 만약 소수가 아니었더라면 또 페르마 인수분해 방법을 써서.. 계속..

이런식으로.. 코딩 하시면 될거에요..
예전에 코딩해 둔게 있긴 있는데 딴데 있군요..
그리고 gnu factor 같은데 쓰인 알고리즘은 엄청 복잡할듯..

hjlee의 이미지

FYI - GNU factor 에서 사용한 알고리즘

wheel factorization 을 사용한다고 되어있군요.

http://primes.utm.edu/glossary/page.php?sort=WheelFactorization

2 와 홀수로 나누는 것도 이 알고리즘이죠 사용 prime [2], wheel size = 2, 50% 정수를 건너 뜀.

GNU factor 에서는 [2,3,5,7,11] 다섯개의 prime 으로 wheel 을 만들고 480/2310 의 정수만 check 합니다. (2310-480)/2310 - 대략 79% 의 정수를 건너뜀.

hsnks100의 이미지

느리지만 재귀로 짜봤습니다.

void factor2(unsigned int r)
{
	if(r<=3)
	{
		printf("%d", r);
		return;
	}
 
	int sqrt_v = sqrt((double)r);
	for(int i=2; i<=sqrt_v; i++)
	{
		if(r % i == 0)
		{
			printf("%d*", i);
			factor2(r/i);
			return;
		}
	}
}

----------------------------------------------------
개인 블로그: https://kangssu.com

dl3zp3의 이미지

다양한 프로그래밍언어로 작성된 소인수분해코드를 더 감상하고프신 분은 Project Euler Problem 3을 풀어서 로그인한 후 답안을 제출해보세요. 그러면 답을 맞춘 사람들만 접속할 수 있는 포럼이 나옵니다.

소인수분해하는 파이썬 코드.

def factors(n):
	"""produces factors
 
	>>> print factors(2 * 2 * 17 * 17 * 17)
	[2, 2, 17, 17, 17]
	"""
        list = []
        i = 2
        while 1:
                while n % i == 0:
                        list.append(i)
                        n = n / i
                if n == 1:
                        break
                elif i * i > n:   # n is products of primes that is > i
                        list.append(n)   # because n is prime, last one.
                        break
                i++
        return list

파이썬 모르는 분은 다음 세 가지만 알면 위 코드를 읽을 수 있다는...

"""에서 두번째 """까지는 주석.
#로 시작하는 부분도 주석.

factors(2 * 2 * 5 * 17 * 17)를 실행할 경우 list의 값과 n의 값은
[], 2 * 2 * 5 * 17 * 17
[2], 2 * 5 * 17 * 17
[2, 2], 5 * 17 * 17
[2, 2, 5], 17 * 17
[2, 2, 5, 17], 17
[2, 2, 5, 17, 17], 1
의 순서로 변화하고 총 나눗셈연산(/, %)은 O(17)번 실행됩니다.
일반적으로 n을 나누는 가장 큰 소수가 p일 때 p * p 가 n을 나누어 떨어지는 경우는 총 나눗셈연산횟수가 O(p)이고 p * p가 n을 나누지 않는 경우는 총 나눗셈연산횟수가 O(sqrt(p)).
이보다 빠른 알고리즘은 없을 것 같다는... 아 물론 i를 돌릴 때, 2가 아닌 짝수는 뛰어넘고 3이 아닌 3의 배수도 뛰어넘는 식으로 하면 더 빨라지긴 하지만, 그래도 O()는 불변.

hjlee의 이미지

http://en.wikipedia.org/wiki/Integer_factorization

큰 수의 소인수 분해 문제는 많은 연구가 이루어지고 있는 분야입니다.
공개키 알고리즘으로 종종사용되는 RSA 알고리즘이 이 문제가 어렵다는 점에 기반하고 있습니다.

물론 아직까지 polynomial 시간에 소인수분해를 할 수 있는 알고리즘은 발견되지 않았기 때문에 RSA 알고리즘을 별다른 염려 없이 사용할 수 있습니다.

GNFS(general number field sieve)가 현재까지 알려진 가장 빠른 알고리즘입니다. 물론 복잡도 측면에서 그렇다는 것이고 100 bit 이하의 숫자는 다른 알고리즘을 사용하는 것이 더 빠르다고 합니다.
복잡도는 위의 글에서
http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity
보시면 그림으로 그려져 있습니다.

님의 알고리즘은 n 이 소인수가 아닌 최악의 경우 (b/2) bit 숫자 두개의 곱인 경우입니다.
대략 O(power(2,(b/4)) =~ O(exp(b)).

--------

작은 수의 경우, wheel factorization 이라는 복잡도는 기본 방법과 별 차이가 없지만, 쉽게 이해할 수 있고, 나눗셈도 현저히 줄일 수 있는 방법이 있습니다.

http://primes.utm.edu/glossary/page.php?sort=WheelFactorization

http://en.wikipedia.org/wiki/Wheel_factorization

--------

(수정 - P.S. 글 쓰고 둘러 보다가 누군가 wheel factorization 에 대해서 먼저 썼구나 했는데... 그게 저이군요... ^^;)

--
http://hjlee-p.blogspot.com/

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.