我自己怎麼寫都跑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;
}

試了三種寫法

寫法一是將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;
} 

仔細看了以後，

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

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

還是我觀念錯誤？

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

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

麻煩幫我看一下，

怎麼測都是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;
}

找出問題了

原來是因為沒有先開根號

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

感謝大大的幫忙︿︿；

 雖然快，但還是逾時。

#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 的範例程式。
* 使用的演算法效率不夠。

如果你想衝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就可以了

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

加油~ 

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

   以下是程式碼 

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

} 

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

更正:是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.     }