현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

소수인지 아닌지 알려주는 프로그램?

세벌의 이미지
글쓴이: 세벌 / 작성시간: 일, 2014/06/15 - 6:26오전

어떤 수를 입력하면 그 수가 소수인지 아닌지 알려주는 프로그램을 찾아 봤습니다. 구글에게 물어보니
http://www.math.com/students/calculators/source/prime-number.htm 이런 게 나오네요.
123456789123456789
가 소수인가 아닌가 해보니... It is divisible by 2. 라고 나오네요. 한 눈에 봐도 짝수는 아닌데...

아주 큰 숫자를 넣더라도 소수인지 아닌지 제대로 알려주는 프로그램은 어떻게 만들면 될까요?

프로그램언어별로 다양한 답이 나올 것 같네요 :)

Forums: 
프로그래밍 QnA
shint의 이미지

글쓴이: shint / 작성시간: 일, 2014/06/15 - 10:26오전

결과가 정확한지는 모르겠고. 비슷한 정도 뿐 입니다. ㅡ_ㅡ;;

댓글 첨부 파일: 
첨부파일 크기
Package icon test 소수와 합성수.zip2.29 MB

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 일, 2014/06/15 - 2:43오후

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

dltkddyd의 이미지

글쓴이: dltkddyd / 작성시간: 일, 2014/06/15 - 2:55오후

너무 막연합니다. 어차피 타입이라는 것이 한정된 공간을 사용하는 것이잖아요. 제일 큰 공간을 사용하는 타입의 한계를 극복하려면 클래스로 사용자 정의 타입을 새롭게 만드셔야겠군요. 일전에 제가 복사생성자에 대해 언급할 때 형식매개변수로 레퍼를 사용하지 않는 클래스는 대단하다는 말씀을 드린 적이 있습니다. 그 때 대부분 그 말 뜻을 이해하지 못하더군요. 레퍼런스가 느리다는 것을 말한 것이 아닙니다. 바로 새로운 타입이라는 관점에서 말씀드린 것이죠. 물론 레퍼런스로 형식매개변수를 사용하지 않을 경우에 해당 타입이 너무 커서는 곤란하다는 점을 말씀드리죠.

본인 맞습니다.
인증샷
우헤헤헤... 로 대신합니다.

kaeri17의 이미지

글쓴이: kaeri17 / 작성시간: 일, 2014/06/15 - 6:11오후

소수 판별은 NP문제라고 알려져 있습니다. 몇몇 특별한 경우를 제외하곤, 소수인지 판별하는 알고리즘은 기본적으로 그 수의 root되는 수까지 계속 나눠보는 방법 뿐입니다. 결국 숫자가 커질수록 exponential하게 계산량이 많아질수 밖에 없습니다.

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 일, 2014/06/15 - 6:13오후

판별 자체는 P 문제입니다.

kaeri17의 이미지

글쓴이: kaeri17 / 작성시간: 일, 2014/06/15 - 6:33오후

엇 그러네요.. 암호론을 대강들었더니 이런 기본적인게 헷갈렸군요...

kaeri17의 이미지

글쓴이: kaeri17 / 작성시간: 일, 2014/06/15 - 6:41오후

위에 댓글을 보고 찾아보니 알고리즘들이 많군요. 이런 종료의 문제를 임의의 큰수에 대해서 가장 간단하게 하는 방법은 python을 쓰는거죠. C/C++이라면 GMP를 써서 조금 귀찮게 구현할 수 있습니다.

dltkddyd의 이미지

글쓴이: dltkddyd / 작성시간: 월, 2014/06/16 - 12:50오전

약수가 1과 자기 자신 밖에 없는 수를 소수라고 하잖아요. 그러면 2부터 (그 자신-1)까지 반복문을 돌리면서 나머지가 0이 나오면 소수가 아닌 것으로 판별하면 되지 않을까요? 

/*의사코드*/
bool is_prime_number=true;
for(unsigned long int i=2;i<=(그 자신-1);i++) {
    unsigned long int remainder=(그 자신%i);
    if(remainer==0) {
        is_prime_number=false;
        break;
    }
}

저런 알고리즘도 속도를 더 개선할 수 있는 여지가 있겠군요. 예컨데 그 자신을 절반으로 나눈 값을 사용하시면요.

본인 맞습니다.
인증샷
우헤헤헤... 로 대신합니다.

gilgil의 이미지

글쓴이: gilgil / 작성시간: 월, 2014/06/16 - 3:11오전

1~root(n)까지만 확인해도 된다고 위에서 kaeri17님이 말씀하셨는데요.

www.gilgil.net

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.