試了很多方法，包含建表、6N判斷、210N判斷，
也用了開根號的技巧，
但就過不了？

最後甚至 copy 討論區的程式碼貼上，果不其然還是過不了
我的程式都逾時(2sec)，而討論區的 code 說可以 30ms ...
這是很糟糕的示範= =

附上我過不了的程式碼

#include <iostream>
#include <cstdlib>
#include <math.h>
#include <bitset>

const int Size = 46342; // 質數表可處理的大小

bool PrimeTable[Size]; // 陣列初始值都設 false
// false 表示質數
// true 表示非質數
// 第偶數個元素不理他

void GeneratePrimeTable()
{
    PrimeTable[0] = PrimeTable[1] = true;
    int max = (int)sqrt(Size) + 1;
    for(int i = 3 ; i < max ; i += 2) // 利用 埃拉托斯特尼篩法 建質數表
    {
        if(!PrimeTable[i])
        {
            int delta = (i << 1);
            for(int j = i*i ; j < Size ; j += delta)
            {
                PrimeTable[j] = true;
            }
        }
    }
}

bool PrimeTableTest(int n)
{
    if(n == 2)return true;
    if(n%2 == 0)return false;
    if(n < Size)return !PrimeTable[n];

    int max = (int)sqrt(n) + 1;
    for(int i = 3 ; i < max ; i +=2)
    {
        if(!PrimeTable[i] && n%i == 0)return false;
    }
    return true;
}

int main()
{
    GeneratePrimeTable();
    int n;
    while(std::cin >> n)
    {
        if(PrimeTableTest(n))
            std::cout << "質數" << std::endl;
        else
            std::cout << "非質數" << std::endl;
    }
};

這題非常怪異,我試了很久自己寫的程式,結果都是TLE程式超時

後來不死心拿google出來的程式碼執行也是TLE...

不曉得問題在哪裡

#include<stdio.h>
#include<math.h>

#define MAX 65537
int prime[6542],len=0 ;

void set_prime(){
prime[len++]=2 ;
for (int i=3 ;i<MAX;i+=2 ){
bool ok=1 ;
for (int j=0 ,k=floor(sqrt(i)) ;prime[j]<=k ;j++ )if (i%prime[j]==0){
ok=0 ;
break ; 
}
if (ok)prime[len++]=i ;
}
}

bool is_prime(int n){
for (int i=0 ,k=floor(sqrt(n));prime[i]<=k;i++ )
if (n%prime[i]==0)return 0 ;
return 1 ;
}

int main(){
set_prime() ;

int n ;
while (~scanf("%d",&n)){ 
printf("%s\n",is_prime(n)?"質數":"非質數") ;
}
}

有嗎 我網路上找的程式碼現在貼也是1.2S左右