#419: 請教判斷質數!?


deepking (deepking)

學校 : 不指定學校
編號 : 2206
來源 : [114.27.131.5]
最後登入時間 :
2014-01-17 06:09:37
a007. 判斷質數 | From: [122.122.37.228] | 發表日期 : 2008-07-25 18:14

我自己怎麼寫都跑7Xms左右

我有開根號了,還是沒改善

可是有看到其他人在30ms左右的

 甚至有18.....

請問有人可以分享比較快的寫法嗎?

 

 
#423: Re:請教判斷質數!?


POOHccc ()

學校 : 國立臺中技術學院
編號 : 1139
來源 : [220.135.97.253]
最後登入時間 :
2012-02-04 21:23:42
a007. 判斷質數 | From: [220.135.97.253] | 發表日期 : 2008-07-25 20:35

我自己怎麼寫都跑7Xms左右

我有開根號了,還是沒改善

可是有看到其他人在30ms左右的

 甚至有18.....

請問有人可以分享比較快的寫法嗎?

 

試了三種寫法

寫法一是將sqrt的值給紀錄起來。

寫法二、三是用篩法,所以只要產生sqrt(2147483647) 個質數表(1~46340),但偶數除了2是質數其他都是非質數,所以只要處理3~46340之間是奇數的部分,因此

prime[i] = 0,代表是質數

prime[i] = 1 ,代表是非質數

i 為 3 ~ 46340之間的所有奇數

 

而寫法二和寫法三的不同,寫法三將寫法二的prime[]裡的奇數質數的統統紀錄至prime_table[],因此之後判斷質數只要從prime_table裡尋找並去除(if(n%prime_table[i]==0) return 0;)就行了

 

至於18,看看有沒有高手願意分享

 

【寫法一】 

//       AC  (42ms, 336KB)
#include <stdio.h>
#include <math.h>

int isprime(int n){
    int i,temp;

    if(n==2) return 1;
    if(n%2==0) return 0;

    temp=(int)sqrt((double)n);
    for(i=3;i<=temp;i+=2)
        if(n%i==0)
            return 0;

    return 1;
}

int main(){
    int x;

    while(scanf("%d",&x)==1){
        if(isprime(x)) puts("質數");
        else puts("非質數");
    }

    return 0;
}

 

【寫法二】

//        AC  (30ms, 506KB)
#include <stdio.h>
#include <math.h>

#define MAXSIZE    46340

int prime[MAXSIZE+1];

int makeprime(){
    int i,j;
   
    for(i=3;i<=MAXSIZE;i+=2)
        if(!prime[i])
            for(j=i+i;j<=MAXSIZE;j+=i)
                prime[j]=1;
}

int isprime(int n){
    int i,temp;

    if(n==2) return 1;
    if(n%2==0) return 0;
    if(n<=MAXSIZE){
        return 1-prime[n];
    }

    for(i=3;i<=MAXSIZE && i*i<=n;i+=2)
        if(!prime[i] && n%i==0)
            return 0;

    return 1;
}

int main(){
    int x;

    makeprime();
    while(scanf("%d",&x)==1){
        if(isprime(x)) puts("質數");
        else puts("非質數");
    }

    return 0;
}

 

【寫法三】

//        AC  (24ms, 538KB)
#include <stdio.h>
#include <math.h>

#define MAXSIZE    46340

int prime[MAXSIZE+1];
int prime_table[MAXSIZE],prime_table_len=0;

int makeprime(){
    int i,j;
   
    for(i=3;i<=MAXSIZE;i+=2)
        if(!prime[i]){
            for(j=i+i;j<=MAXSIZE;j+=i)
                prime[j]=1;

            prime_table[prime_table_len++]=i;
        }
}

int isprime(int n){
    int i,temp;

    if(n==2) return 1;
    if(n%2==0) return 0;
    if(n<=MAXSIZE){
        return 1-prime[n];
    }

    for(i=0;i!=prime_table_len && prime_table[i]*prime_table[i]<=n;++i)
        if(n%prime_table[i]==0)
            return 0;

    return 1;
}

int main(){
    int x;

    makeprime();
    while(scanf("%d",&x)==1){
        if(isprime(x)) puts("質數");
        else puts("非質數");
    }

    return 0;
}

 
#426: Re:請教判斷質數!?


deepking (deepking)

學校 : 不指定學校
編號 : 2206
來源 : [114.27.131.5]
最後登入時間 :
2014-01-17 06:09:37
a007. 判斷質數 | From: [122.122.33.171] | 發表日期 : 2008-07-25 23:55

我自己怎麼寫都跑7Xms左右

我有開根號了,還是沒改善 

可是有看到其他人在30ms左右的

 甚至有18.....

請問有人可以分享比較快的寫法嗎?

 

試了三種寫法

寫法一是將sqrt的值給紀錄起來。

寫法二、三是用篩法,所以只要產生sqrt(2147483647) 個質數表(1~46340),但偶數除了2是質數其他都是非質數,所以只要處理3~46340之間是奇數的部分,因此

prime[i] = 0,代表是質數

prime[i] = 1 ,代表是非質數

i 為 3 ~ 46340之間的所有奇數

 

而寫法二和寫法三的不同,寫法三將寫法二的prime[]裡的奇數質數的統統紀錄至prime_table[],因此之後判斷質數只要從prime_table裡尋找並去除(if(n%prime_table[i]==0) return 0;)就行了

 

至於18,看看有沒有高手願意分享 

 

【寫法一】 

//       AC  (42ms, 336KB) 
#include <stdio.h>
#include <math.h>

int isprime(int n){
    int i,temp;

    if(n==2) return 1;
    if(n%2==0) return 0;

    temp=(int)sqrt((double)n);
    for(i=3;i<=temp;i+=2)
        if(n%i==0)
            return 0;

    return 1;
}

int main(){
    int x;

    while(scanf("%d",&x)==1){
        if(isprime(x)) puts("質數");
        else puts("非質數");
    }

    return 0;
}

 

【寫法二】

//        AC  (30ms, 506KB) 
#include <stdio.h>
#include <math.h>

#define MAXSIZE    46340

int prime[MAXSIZE+1];

int makeprime(){
    int i,j;
    
    for(i=3;i<=MAXSIZE;i+=2)
        if(!prime[i])
            for(j=i+i;j<=MAXSIZE;j+=i)
                prime[j]=1;
}

int isprime(int n){
    int i,temp;

    if(n==2) return 1;
    if(n%2==0) return 0;
    if(n<=MAXSIZE){
        return 1-prime[n];
    }

    for(i=3;i<=MAXSIZE && i*i<=n;i+=2)
        if(!prime[i] && n%i==0)
            return 0;

    return 1;
}

int main(){
    int x;

    makeprime();
    while(scanf("%d",&x)==1){
        if(isprime(x)) puts("質數");
        else puts("非質數");
    }

    return 0;

 

【寫法三】 

//        AC  (24ms, 538KB) 
#include <stdio.h>
#include <math.h>

#define MAXSIZE    46340

int prime[MAXSIZE+1];
int prime_table[MAXSIZE],prime_table_len=0;

int makeprime(){
    int i,j;
    
    for(i=3;i<=MAXSIZE;i+=2)
        if(!prime[i]){
            for(j=i+i;j<=MAXSIZE;j+=i)
                prime[j]=1;

            prime_table[prime_table_len++]=i;
        }
}

int isprime(int n){
    int i,temp;

    if(n==2) return 1;
    if(n%2==0) return 0;
    if(n<=MAXSIZE){
        return 1-prime[n];
    }

    for(i=0;i!=prime_table_len && prime_table[i]*prime_table[i]<=n;++i)
        if(n%prime_table[i]==0)
            return 0;

    return 1;
}

int main(){
    int x;

    makeprime();
    while(scanf("%d",&x)==1){
        if(isprime(x)) puts("質數");
        else puts("非質數");
    }

    return 0;


仔細看了以後,

我發現我的程式碼跟你的差別在有沒有副程式!

分開在副程式寫不是應該會比較慢嗎?

還是我觀念錯誤?

 
#427: Re:請教判斷質數!?


POOHccc ()

學校 : 國立臺中技術學院
編號 : 1139
來源 : [220.135.97.253]
最後登入時間 :
2012-02-04 21:23:42
a007. 判斷質數 | From: [220.135.97.253] | 發表日期 : 2008-07-26 06:08

應該不是差別在有沒有副程式的關係唷

你要不要貼一下程式碼,讓我們研究一下問題在那呢?

 
#428: Re:請教判斷質數!?


deepking (deepking)

學校 : 不指定學校
編號 : 2206
來源 : [114.27.131.5]
最後登入時間 :
2014-01-17 06:09:37
a007. 判斷質數 | From: [122.122.34.24] | 發表日期 : 2008-07-26 06:52

麻煩幫我看一下,

怎麼測都是7x...

#include<stdio.h>
#include<math.h>
 int main(void)
 {     int num,i,temp;
     while(scanf("%d",&num)==1){
         if(num==2)
             printf("質數\n");
         else if(num%2==0)
             printf("非質數\n");
         else
         {
             temp=1;
             for(i=3;i<=sqrt(num);i+=2){
                 temp=1;
                 if(num%i==0){
                     printf("非質數\n");
                     temp=0;
                     break;
                 }
             }
             if(temp)
                 printf("質數\n");
         }
     }
     return 0;
}

 
#429: Re:請教判斷質數!?


deepking (deepking)

學校 : 不指定學校
編號 : 2206
來源 : [114.27.131.5]
最後登入時間 :
2014-01-17 06:09:37
a007. 判斷質數 | From: [122.122.34.24] | 發表日期 : 2008-07-26 07:42

找出問題了

原來是因為沒有先開根號

先在for外面開好根號就有3x了

感謝大大的幫忙︿︿;

 
#735: Re:請教判斷質數!?


h4x (h4x)

學校 : 中国天津一中
編號 : 3360
來源 : [60.30.82.162]
最後登入時間 :
2009-12-18 21:22:50
a007. 判斷質數 | From: [60.30.82.162] | 發表日期 : 2008-10-24 22:24

我自己怎麼寫都跑7Xms左右

我有開根號了,還是沒改善 

可是有看到其他人在30ms左右的

 甚至有18.....

請問有人可以分享比較快的寫法嗎?

 

 Miller-Rabin素性測試你有用過嗎?
 
#1094: Re:請教判斷質數!?


spider458 (beginer)

學校 : 高雄市立高雄高級中學
編號 : 2895
來源 : [218.164.9.166]
最後登入時間 :
2010-08-18 08:40:17
a007. 判斷質數 | From: [218.169.194.16] | 發表日期 : 2008-12-23 21:03

 雖然快,但還是逾時。

#include<iostream>
using namespace std;
int main(){
    int n, s=0, i;
     while(cin >> n)
      { for (i=1; i<n; i++)
        {
         if ( n%i==0 ) s+=i;
        }
        if ( s==1 ) cout << "質數" << endl;
         else cout << "非質數" << endl;
      }
return 0;
}

 執行逾時(1s)!! 請檢查是否產生無限迴圈或尋找更好的演算法
可能原因為:
* 讀取測資視時未考慮到 EOF 導致等待過久,請參考 a001 的範例程式。
* 使用的演算法效率不夠。

 
#1099: Re:請教判斷質數!?


su_horng (su_horng)

學校 : 劍橋大學國王學院
編號 : 1089
來源 : [111.248.42.147]
最後登入時間 :
2014-12-13 21:15:21
a007. 判斷質數 | From: [220.137.68.60] | 發表日期 : 2008-12-24 21:47

你根本沒開根號耶.....? 
#1913: Re:請教判斷質數!?


elct9620 (弦夜)

學校 : 桃園縣立平鎮高級中學
編號 : 6684
來源 : [59.115.83.14]
最後登入時間 :
2013-12-22 00:38:01
a007. 判斷質數 | From: [122.116.5.186] | 發表日期 : 2009-05-05 21:26

我自己怎麼寫都跑7Xms左右

我有開根號了,還是沒改善

可是有看到其他人在30ms左右的

 甚至有18.....

請問有人可以分享比較快的寫法嗎?

 

我自己也不敢相信,我的結果顯示 6ms

(其實失敗很多次才成功的,各位看看吧!)


/**********************************************************************************/
/* Problem: a007 "判斷質數" */
/* Language: C++ */
/* Result: AC (6ms, 686KB) on ZeroJudge */
/* Author: elct9620 at 2009-05-05 21:21:23 */
/**********************************************************************************/

#include
#include

using namespace std;

int check(int num){
int i,run;
if(num%2 == 0 && num != 2) return true;
run = ceil(sqrt(num));
for(i = 3;i <= run;i+=2){
if(num%i == 0) return true;
}
return false;
}

int main(){
int a;
while(cin >> a){
if(check(a)){
cout << "非質數" << endl;
}else{
cout << "質數" << endl;
}
}
}
 
#1919: Re:請教判斷質數!?


bleed1979 (Bleed)

學校 : 不指定學校
編號 : 1489
來源 : [203.204.21.29]
最後登入時間 :
2021-05-02 22:12:13
a007. 判斷質數 | From: [118.168.128.96] | 發表日期 : 2009-05-06 21:46

我自己怎麼寫都跑7Xms左右

我有開根號了,還是沒改善

可是有看到其他人在30ms左右的

 甚至有18.....

請問有人可以分享比較快的寫法嗎?

 

如果你想衝0ms的話可以考慮以下網頁

http://primes.utm.edu/prove/prove2_3.html 

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

 

基本上我做這題是把ACM UVa的那裡的某題直接拿來改的

所以我做了 2, 3, 5, 7, 11, 13 and 17-SPRP

程式碼寫得很長

以這題的測資來說

應該只要做到2, 3, 5 and 7-SPRP就可以了

縮短程式碼就可以刷新紀錄

加油~ 

 
#3103: Re:請教判斷質數!?


firejox (tangent)

學校 : 國立臺中第一高級中學
編號 : 8517
來源 : [36.235.234.108]
最後登入時間 :
2024-06-11 18:29:29
a007. 判斷質數 | From: [220.133.52.85] | 發表日期 : 2009-12-25 20:31

我自己怎麼寫都跑7Xms左右

我有開根號了,還是沒改善

可是有看到其他人在30ms左右的

 甚至有18.....

請問有人可以分享比較快的寫法嗎?

 


 我也跑出6s了(努力嘗試之下)  

   以下是程式碼 

     /**********************************************************************************/

 

/* Problem: a007 "判斷質數" */
/* Language: C */
/* Result: AC (6ms, 234KB) on ZeroJudge */
/**********************************************************************************/
/* Author: firejox at 2009-12-25 20:23:07 */
#include<stdio.h> #include<math.h> int a; void f(){ int b,c;
e(scanf("%d",&a)!=EOF){
b=(int)sqrt((float)a); for(c=3;c<=b;c+=2){ if(a%c==0){ puts("非質數"); break; } if(c==b||c==b-1)puts("質數"); } } int main(){ whi
l if(a==2||a==5||a==3){ puts("質數"); continue; } switch(a%10){ case 0:puts("非質數"); break; case 2:puts("非質數"); break; case 4:puts("非質數");

break; case 5:puts("非質數"); break; case 6:puts("非質數"); break; case 8:puts("非質數"); break; default :f(); } }

return 0; 

 

} 

 
#3104: Re:請教判斷質數!?


firejox (tangent)

學校 : 國立臺中第一高級中學
編號 : 8517
來源 : [36.235.234.108]
最後登入時間 :
2024-06-11 18:29:29
a007. 判斷質數 | From: [210.60.107.233] | 發表日期 : 2009-12-25 20:35

我自己怎麼寫都跑7Xms左右

我有開根號了,還是沒改善

可是有看到其他人在30ms左右的

 甚至有18.....

請問有人可以分享比較快的寫法嗎?

 


 我也跑出6s了(努力嘗試之下)  

   以下是程式碼     /**********************************************************************************//* Problem: a007 "判斷質數" *//* Language: C *//* Result: AC (6ms, 234KB) on ZeroJudge *//* Author: firejox at 2009-12-25 20:23:07 *//**********************************************************************************/
#include<stdio.h>#include<math.h>int a;void f(){ int b,c; b=(int)sqrt((float)a); for(c=3;c<=b;c+=2){ if(a%c==0){ puts("非質數"); break; } if(c==b||c==b-1)puts("質數"); } }int main(){ while(scanf("%d",&a)!=EOF){ if(a==2||a==5||a==3){ puts("質數"); continue; } switch(a%10){ case 0:puts("非質數"); break; case 2:puts("非質數"); break; case 4:puts("非質數"); break; case 5:puts("非質數"); break; case 6:puts("非質數"); break; case 8:puts("非質數"); break; default :f(); } } return 0;
}
 
#3113: Re:請教判斷質數!?


firejox (tangent)

學校 : 國立臺中第一高級中學
編號 : 8517
來源 : [36.235.234.108]
最後登入時間 :
2024-06-11 18:29:29
a007. 判斷質數 | From: [218.210.138.136] | 發表日期 : 2009-12-26 16:32

我自己怎麼寫都跑7Xms左右

我有開根號了,還是沒改善

可是有看到其他人在30ms左右的

 甚至有18.....

請問有人可以分享比較快的寫法嗎?

 


 我也跑出6s了(努力嘗試之下)  

   以下是程式碼      /**********************************************************************************//* Problem: a007 "判斷質數" *//* Language: C *//* Result: AC (6ms, 234KB) on ZeroJudge *//* Author: firejox at 2009-12-25 20:23:07 *//**********************************************************************************/
#include#includeint a;void f(){int b,c;b=(int)sqrt((float)a);for(c=3;c<=b;c+=2){if(a%c==0){puts("非質數");break;}if(c==b||c==b-1)puts("質數");}}int main(){while(scanf("%d",&a)!=EOF){if(a==2||a==5||a==3){puts("質數");continue;}switch(a%10){case 0:puts("非質數");break;case 2:puts("非質數");break;case 4:puts("非質數");break;case 5:puts("非質數");break;case 6:puts("非質數");break;case 8:puts("非質數");break;default :f();}}return 0;
}


更正:是6ms

外加改良:4ms

  1. #include<stdio.h>   
  2. #include<math.h>   
  3. int a;   
  4. void f(){   
  5.     int b,c;   
  6.     b=(int)sqrt((float)a);   
  7.     for(c=3;c<=b;c+=2){   
  8.             if(a%c==0){   
  9.                 puts("非質數");   
  10.                 break;   
  11.             }   
  12.             if(c==b||c==b-1)puts("質數");   
  13.         }   
  14.     }   
  15. int main(){   
  16.     while(scanf("%d",&a)!=EOF){   
  17.         if(a==2||a==5||a==3)puts("質數");   
  18.         else if(!((a%10)%2)||!((a%10)%5))puts("非質數");   
  19.         else f();   
  20.             }   
  21.     return 0;   
  22.     }  

 

 
ZeroJudge Forum