소수판별 - C# & C++

　본 게시물은 Naver 블로그에서 이동해온 글입니다.

소수를 찾는 프로그램 입니다.

(자신이 입력해서 소수면 소수라고 뜹니다.)

이 프로그램의 코드를 원하시면 덧글로 달아주세요~

수정전

소수 판별.exe

글에 붙은 덧글 .

• txblade 2011/10/10 12:51답글|삭제|신고

  1억이상부터는 좀 오래 걸리네요..(4초이상걸림) 숫자 하나 찾는건데 ㅜ ㅜ
  찾고자하는 숫자의 제곱근까지의 수로 그 수를 나눠가면서 찾는다고하면
  1억이면 1만까지로 찾으면 0.1초도 안걸릴텐데 좀 아쉽네요

• 

  몰모티 2011/10/10 16:22답글|수정|삭제

  애초에 컴퓨터니깐 오래걸린다고 느끼는거지
  사람으로치면 엄청 빠른거죠
  
  
  근데 그건 알고리즘 + CPU 문제 ㅋ
  
  근데 찾고자하는 숫자를 찾아야하는데 " 찾고자하는 숫자의 제곱근 " 은 미지수이지 않나요?
  뭐, 제가 정확히 이해하지 못한것일수도 있겠네요

• 

  txblade 2011/10/10 22:49답글|삭제|신고

  1억을 예로 듭시다
  
  1억은 소인수가 좀 많긴 하지만
  프로그램 짤때 만약 1억까지 모든수로 다 나누면
  나머지가 모두 0이 아닐때 소수로 짤텐데요 시간이 너무 걸리죠...
  1억의 제곱근인 1만을 넘는 수로는 나눠줄 필요가 전혀 없습니다
  
  소인수를 가지는 수의 경우 항상
  a*b=n의 식을 가지는데요(a,b는 1보다큰 자연수, n은 소인수를 가지는수)
  100의 경우 
  2,4,5,10,20,25,50에서 제곱근인 10이 넘는 20,25,50으로도 나눠지지만
  각자 곱해지는 짝(2-50, 4-25, 5-20)이 있기때문에 제곱근보다 큰 수로는 나눠줄 필요가 전혀 없습니다
  (제곱근보다 작은 수로 나눠진다는 말은, 그 작은수와 곱해지는 다른 큰 수가 존재한다는 말.
  즉 제곱근보다 작은 수로 나눠보면 됩니다)
  이런식으로 [소수인지판별하고싶은수의 제곱근]을 이용하면 수가 커질수록 속도는 수배도 아니고 수배의수제곱으로 빨라지죠
  
  2,999,999
  이 수는 소수인데요(엄청 크죠?)
  만약 2부터 2999999까지 일일이 나눈다면 효율이 좀 많이 떨어집니다
  2999999의 제곱근보다 작거나 같은수로 전부 나눴는데도 나머지가 전부 0이 아니면
  결국 이수는 소인수가 존재하지 않는다는것이 되고요
  그 윗수는 나눠줄 필요자체가 없습니다.
  2999999의 제곱근은 1730이 조금 넘는데
  1750정도 까지 나눴는데도 전부 나누어떨어지지 않는다면
  그 윗수로 나눠질 턱이 없죠
  그 윗수와 곱해질 1~1750까지의 수가 없으니까요
  
  최종정리
  2999999의 제곱근 보다 작거나 같은 수를 전부 나눴는데도(약 1735까지) 나누어떨어지지않으면
  제곱근보다 큰수(제곱근보다 큰수를 서로 곱하면 반드시 2999999이상이 나오기 때문)
  로 나눌 필요가 없어지는것.

• 

  txblade 2011/10/10 22:51답글|삭제|신고

  아무리 슈퍼컴퓨터라도 수조 단위의 소수를 계산하려면
  모든 방법을 통동원해서 계산을 간단히 만들어 주는게 필수죠
  이방법외에도 많으나 저는 아직 제꺼로 못만들었네요(소수는 정말 난제임..어려움 ㅇ_ㅇ)

• 

  몰모티 2011/10/10 23:14답글|수정|삭제

  아하 , 이해 됬습니다.
  
  좋은 방법이네요, 언제 한번 실험해보겠습니다. 감사해요 ^^[ '' 잠시만 기다리세요 c++로 짜서 한번 올려볼게요 ]
  
  
  //
  
  아? , 짜다보니깐 문제점이 있네요.
  제곱근으로 정확히 나뉘어지지 않는 숫자는 판별이 부정확해지다는점이나
  애초에 소인수분해는 제곱근넘어서 까지 구하는것이니깐요.
  예를들어 16 = 1, 2, 4, 8, 16
  
  고로, 틀린 논리라고 생각합니다.
  
  //
  는 잠만, 다시한번 봐야겠네요
  한번 더 읽어보니 맞을거같기도.. 미치네
  
  //
  아, 됬습니다.
  프로그램 올리겠습니다 ^^
  두번째 말은 무시해주세요 ~!
  이해가 반밖에 안된채로 나불댄거니.. ㅠ

• 

  몰모티 2011/10/10 23:50답글|수정|삭제

  http://blog.naver.com/lunar_demon_/60143434721
  그대로 코딩했습니다.
  
  확인해보시고 문제점있으면 또 지적해주시면 감사하겠습니다 (__ )

• 

  txblade 2011/10/11 12:07답글|삭제|신고

  비밀 답글입니다.

  몰모티 헐..지적까지야,, 저도 초보랍니다 ㅜ ㅜ
  c플소스로 위에 첨부파일처럼 프로그램 만드는방법이 궁금한데,,,(저도 c플을 배우고있어서)
  메일로 방법좀..안될까요 ㅎㅎ

• 

  몰모티 2011/10/11 16:38답글|수정|삭제

  비밀 답글입니다.

  txblade 디버깅 한다음에 소스하고 같은 폴더에 Debug라는 폴더가생깁니다.
  
  들어가서 .exe 확장자 찾으시면 나와요 ㅎ

• 

  txblade 2011/10/12 11:13답글|삭제|신고

  비밀 답글입니다.

  몰모티 아..ctrl+f5누르면 나오는거네요
  그거말고 위에처럼 진짜 프로그램으로 만들려면 어떻게하지용?
  버튼도있고 막..
  버튼도 코딩이 될라나염?

• 

  몰모티 2011/10/12 16:31답글|수정|삭제

  비밀 답글입니다.

  txblade C++ API를 사용하는법도 있지만
  전 귀찮아서리 C# 배우고 있습니다 ㅎ
  
   

 
그리고 충고를 받아 수정한 알고리즘을 적용
 

  
#include "stdio.h"
#include "math.h"
void main()
{
 int a, num = 0, sum = 0, answer = 0,p;
 printf("소수 판별을 위한 수를 넣어주세요.\n입력 : ");
 scanf("%d",&num);
 a = sqrt(num);
 for (p = 1; p < a+1 ; p++)
    {
        sum = num % p;
        if (sum == 0)
        {
   answer+=2;   
  }
  else{}
 }
 if(answer == 2)
 {
  printf("숫자 [ %d ] 는 소수입니다.\n", num);
 }
 else
 {
  printf("숫자 [ %d ] 는 합성수입니다.\n", num);
 }
}

수정 후

txblade.exe

txtblade님 감사합니다 !