[問題] 判斷質數

[doooo (不入之森)]

     我想請問這個程式要怎麼寫
     由鍵盤輸入一數字  然後判斷此數字是否為質數
     或是可不可以有沒有高手可以幫我找一下
     我的邏輯錯在哪裡  > <
     怎麼寫都跑不出來阿~~    Orz
     謝謝大家  (拜)

     好吧我就把我狗屁不通的程式碼貼出來了
     各位大大不要笑我  我是新新新手阿  > <



int main()
{
  int m,n;
  printf("Please Enter an integer:\n");
  scanf("%d",&n);
  for(m>1;m<n;m++)
 {
  if(n%m==0)
         printf("%d is not a prime!\n",n)
       break;
  else
     printf("%d is a prime!\n",n);
  }
  system("pause");
  return 0;
}

推 csftwpt:Code 在哪裡 XD?
推 endl:國王的新code...
※ 編輯: doooo           來自: 61.230.142.180       (07/10 21:20)
推 bobhsiao:for(m=1;..才對，還有要整個迴圈跑完才算質數
→ cloudrick:要 m=2
> -------------------------------------------------------------------------- <

作者: renderer (rendering) 看板: C_and_CPP
標題: Re: [問題] 判斷質數
時間: Sun Jul 10 21:54:52 2005

※ 引述《doooo (不入之森)》之銘言：
: int main()
: {
:   int m,n;
:   printf("Please Enter an integer:\n");
:   scanf("%d",&n);
:   for(m>1;m<n;m++)
        ^^^
        m=2   // m 需要一個初始值  m>1 是一個邏輯判斷式 無法給m一個初始值
:  {
:   if(n%m==0)
    {
:          printf("%d is not a prime!\n",n)
:        break;
    } // if 下兩個 statement 以上就要用 {} 了
:   else
:      printf("%d is a prime!\n",n);
:   }
:   system("pause");
:   return 0;
: }


  另外 程式的邏輯調整一下：

    bool 是質數 = true;
    for(m=2; m<n; ++m)
    {
      如果 n%m==0 的話
      {
        是質數 = false;
        break;
      }
    }

    if( 是質數 )
      printf(...);
    else
      printf(...);


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.217.9

> -------------------------------------------------------------------------- <

作者: dw5468 (弄雲) 看板: C_and_CPP
標題: [問題] 判斷質數
時間: Tue Nov 29 00:57:21 2005

這是判斷使用者輸入是否為質數的程式

但是當我輸入2、3、5、7時會判斷不出來

11之後的質數他都可以正確判斷

可以麻煩各位幫我看一下我哪邊有寫錯嗎

使用環境是 Visual C++ 6.0

用的語言是C

謝謝！

void main(void)
{
        int x;

        printf("Input a number: ");
        scanf("%d",&x);
    if(x%x==0 && x%2!=0 && x%3!=0 && x%5!=0 && x%7!=0){
                printf("%d is a prime number",x);
        }else{
                printf("%d is not a prime number",x);
        }


}


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.134.242.12
推 windows2k:先去把質數定義看清楚吧
推 kangta198109:應該不能這樣做吧,prime有無限多個ㄟ,另外2%2==0所以
→ kangta198109:會找不到2...依此類推...
推 aecho:推一樓
推 flashliqu:你真的是大學生嗎.........
推 GameDemon:推五樓
推 SPower:ha....
推 gdgy:原po別氣餒，想一想，多看看別人寫的例子
→ Knighter:直接印2 3 5 7不就好了
→ Knighter:直接先印2 3 5 7 就好了,因為if ==2 3 5 7時印出即可
> -------------------------------------------------------------------------- <

作者: aecho (星空下的鮪魚) 看板: C_and_CPP
標題: Re: [問題] 判斷質數
時間: Tue Nov 29 01:02:46 2005

※ 引述《dw5468 (弄雲)》之銘言：
: 11之後的質數他都可以正確判斷
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        我懷疑你這一句話

        143 (13 x 11)
        201 (19 x 11)

        這兩個都不是prime....

        不過你的程式應該都會當成prime吧

: 用的語言是C
: 謝謝！
: void main(void)
: {
:         int x;
:         printf("Input a number: ");
:         scanf("%d",&x);
:     if(x%x==0 && x%2!=0 && x%3!=0 && x%5!=0 && x%7!=0){
:                 printf("%d is a prime number",x);
:         }else{
:                 printf("%d is not a prime number",x);
:         }
: }

--

        「當我真心追尋著我的夢想時，每一天都是繽紛的。
            因為我知道每一個小時都是在實現夢想的一部分，
      當我真實地在追尋著時，一路上我都會發現從未想像過的東西，
如果當初我沒有勇氣去嘗試看來幾乎不可能的事，如今我就還只是個牧羊人而已。」

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.166.85.55

> -------------------------------------------------------------------------- <

作者: hwhs () 站內: C_and_CPP
標題: Re: [問題] 判斷質數
時間: Tue Nov 29 03:20:52 2005

※ 引述《aecho (星空下的鮪魚)》之銘言：
: ※ 引述《dw5468 (弄雲)》之銘言：
: : 11之後的質數他都可以正確判斷
:   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
:         我懷疑你這一句話
:         143 (13 x 11)
:         201 (19 x 11)
:         這兩個都不是prime....
:         不過你的程式應該都會當成prime吧
: : 用的語言是C
: : 謝謝！
: : void main(void)
: : {
: :         int x;
: :         printf("Input a number: ");
: :         scanf("%d",&x);
: :     if(x%x==0 && x%2!=0 && x%3!=0 && x%5!=0 && x%7!=0){
: :                 printf("%d is a prime number",x);
: :         }else{
: :                 printf("%d is not a prime number",x);
: :         }
: : }

依照prime的定義，應該將程式改寫成下面這樣～

#include <stdio.h>

int main()
{
        int x, flag, i;

        printf( "Input a number : " );
        scanf( "%d", &x );

        flag = 0;

        if (x < 2)
                return 0;

        for (i = 2; i < x/2; i++)
        {
                if (x%i == 0)
                {
                        flag = 1;
                        break;
                }
        }

        if (flag == 1 && x != 2)
                printf( "%d is not a prime.", x );
        else
                printf( "%d is a prime.", x );

        return 0;
}

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.248.242

> -------------------------------------------------------------------------- <

作者: wait (ξ~反覆記號~ξ) 看板: C_and_CPP
標題: Re: [問題] 判斷質數
時間: Tue Nov 29 10:23:35 2005

※ 引述《dw5468 (弄雲)》之銘言：
: 這是判斷使用者輸入是否為質數的程式
: 但是當我輸入2、3、5、7時會判斷不出來
: 11之後的質數他都可以正確判斷
: 可以麻煩各位幫我看一下我哪邊有寫錯嗎
: 使用環境是 Visual C++ 6.0
: 用的語言是C
: 謝謝！
=.=" 大家都想太深入了...

int value(int num){
        int i;
        for(i=2;i<num/2;i++){
                if(num%i==0){
                        return 0;
                        break;}
                else if(num/2==i+1){
                        return 1;
                        break;}
        }
}

這樣就可以了 判斷質數function

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.129.64.169
推 hichcock:為什麼不是num開根號 ??
推 hichcock:這樣真的可以嗎??
推 kuoy:因為num只會被1和num整除  判斷到num/2只是多跑了一些數
→ kuoy:上面程式有跑2到 根號num 的數  所以OK...
推 ForeverOrz:應該要用DP來解吧？  做一個buffer存已經找到的prime
→ ForeverOrz:雖然我不知道這篇的效率和用DP的效率是差多少 ( - -)
→ gdgy:他只是要查輸入是否為質數 而不要是建質數表 buffer的用意是?
→ hardcover:dp是指dynamic programming? 好像和dp 沒什關聯說 XD
推 kuoy:上面的質數判斷是較直接易懂的方法...
→ kuoy:還有一些較有效率的方法,不過程式就沒那麼直觀
推 dreamweaver:當輸入2.3時,for迴圈的條件不是不合,為什麼可以跑進去
→ dreamweaver:還有當我輸入4和5時,為什麼回傳2?compiler壞了?不會吧
推 wait:回樓上return 2? 這不可能的 請你檢查 因為return 只有0 or 1
推 wait:還有抱歉 我似乎少一個等號
→ wait:        for(i=2;i<=num/2;i++){
→ wait:這樣就可以了
> -------------------------------------------------------------------------- <

作者: geniuswen (firejimtracy.com) 看板: C_and_CPP
標題: Re: [問題] 判斷質數
時間: Tue Nov 29 15:29:13 2005

我之前寫的

#include<stdio.h>

void main()
{


int k,a,i,j=0;

printf("please Key in Number:\n");
scanf("%d",&a);
for(k=1;k<=a;k++)
{
 for(i=1;i<k;i++)
 {
  if(k%i!=0)
  j++;
  else
  j=0;
 }
if(j==k-2)
printf("%d,",k);
}


}

※ 引述《wait (ξ~反覆記號~ξ)》之銘言：
: ※ 引述《dw5468 (弄雲)》之銘言：
: : 這是判斷使用者輸入是否為質數的程式
: : 但是當我輸入2、3、5、7時會判斷不出來
: : 11之後的質數他都可以正確判斷
: : 可以麻煩各位幫我看一下我哪邊有寫錯嗎
: : 使用環境是 Visual C++ 6.0
: : 用的語言是C
: : 謝謝！
: =.=" 大家都想太深入了...
: int value(int num){
:         int i;
:         for(i=2;i<num/2;i++){
:                 if(num%i==0){
:                         return 0;
:                         break;}
:                 else if(num/2==i+1){
:                         return 1;
:                         break;}
:         }
: }
: 這樣就可以了 判斷質數function

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.168.186.185
→ geniuswen:主要是提供大家一種判斷質數的方法啦
推 hichcock:我記得之前學密碼學的時候有學過一種質數分析法
→ hichcock:效率很快.....不過太久沒碰....忘記了
推 dw5468:真是不好意思...謝謝大家幫忙^^"
推 ckclark:是 a^(p-1) ≡1 (mod p)吧(for a<p) 不過是有死角在的
> -------------------------------------------------------------------------- <

作者: DarkKiller (System hacked) 看板: C_and_CPP
標題: Re: [問題] 判斷質數
時間: Wed Nov 30 07:59:16 2005

※ 引述《geniuswen (firejimtracy.com)》之銘言：
: 推 hichcock:我記得之前學密碼學的時候有學過一種質數分析法           11/29 16:23
: → hichcock:效率很快.....不過太久沒碰....忘記了                    11/29 16:23
: 推 dw5468:真是不好意思...謝謝大家幫忙^^"                           11/29 21:24
: 推 ckclark:是 a^(p-1) ≡1 (mod p)吧(for a<p) 不過是有死角在的      11/30 00:09

這是 Fermat's little theorem。

我們定義 Carmichael number：如果對於所有的 1 < a < p 都符合 Fermat's
little Theorem，但是 a 卻不是質數，則 a 被稱為 Carmichael number。

定理告訴我們，當 n 夠大的時候，1~n 裡面大約有 n^(2/7) 個 Carmichael
number，這個數字對於 Primality test 來說太高了，所以實際上在測試的時
候都不會用 Fermat's little theorem。

比較簡單的有 Miller-Rabin primality test。如果 a 是合數，Miller-Rabin
每做一次就可以保證有 3/4 的機會會判斷出這個數是合數，於是當測試次數愈
來愈多的時候，錯誤率會降到 4^(-k)。

詳細的演算法看 Wikipedia 比較快：
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

如果看不懂的話，問個研究 Cryptography 的教授都應該會知道這個演算法。


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.54.119
推 hichcock:就是這個....MR test....之前寫程式就讓他測個10次
→ hichcock:幾乎都很準了