發表新討論
#7088: TLE


jameskutw (james)

學校 : 臺北市立麗山高級中學
編號 : 23688
來源 : [61.228.178.234]
最後登入時間 ：
2024-01-31 12:18:11
d362. 10394 - Twin Primes -- UVa10394 | From: [220.136.190.121] | 發表日期 : 2012-10-21 16:38
#include <cstdlib>
#include <cstdio>
#include <math.h>
main(){
    
    bool *f=new bool[20000000];
    
    for(int i=0;i<20000000;++i)
    f[i]=1;
    
    f[0]=0;
    f[1]=0;
    
    int m;
    int in;
    int s=0;
    m=(int)sqrt(20000000);
    
    for(int i=2;i*2<20000000;i++)
    f[i*2]=0;
    
    for(int i=3;i<=m;i+=2){
        if(f[i])
        for(int j=3;(j*i)<20000000;j+=2)
        f[j*i]=0;
                       }
        
        
        
        while(scanf("%d",&in)!=EOF){
            for(int i=2;i<20000000;i++){
                if(f[i]&&f[i+2]){
                    s++;
                    }
                    
                    if(s==in)
                    {printf("(%d, %d)\n",i,i+2);
                    s=0;
                    break;}
                }
            }
        
    
    

return 0;
}
 
自己測第100000對馬上就跑出來了
怎麼會TLE？
要怎麼更快 
 
#7089: Re:TLE


jameskutw (james)

學校 : 臺北市立麗山高級中學
編號 : 23688
來源 : [61.228.178.234]
最後登入時間 ：
2024-01-31 12:18:11
d362. 10394 - Twin Primes -- UVa10394 | From: [220.136.190.121] | 發表日期 : 2012-10-21 16:51
#include <cstdlib>
#include <cstdio>
#include <math.h>
main(){
    
    bool *f=new bool[20000000];
    
    for(int i=0;i<20000000;++i)
    f[i]=1;
    
    f[0]=0;
    f[1]=0;
    
    int m;
    int in;
    int s=0;
    m=(int)sqrt(20000000);
    
    for(int i=2;i*2<20000000;i++)
    f[i*2]=0;
    
    for(int i=3;i<=m;i+=2){
        if(f[i])
        for(int j=3;(j*i)<20000000;j+=2)
        f[j*i]=0;
                       }
        
        
        
        while(scanf("%d",&in)!=EOF){
            for(int i=3;i<20000000;i+=2){
                if(f[i]&&f[i+2]){
                    s++;
                    }
                    
                    if(s==in)
                    {printf("(%d, %d)\n",i,i+2);
                    s=0;
                    break;}
                }
            }
        
    
    

return 0;
}
 
 
改成這樣還是3s
不是應該會兩倍速度嗎= = 
 
#7090: Re:TLE


jameskutw (james)

學校 : 臺北市立麗山高級中學
編號 : 23688
來源 : [61.228.178.234]
最後登入時間 ：
2024-01-31 12:18:11
d362. 10394 - Twin Primes -- UVa10394 | From: [220.136.190.121] | 發表日期 : 2012-10-21 17:13
#include <cstdlib>
#include <cstdio>
#include <math.h>
main(){
    
    bool *f=new bool[20000000];
    int tp[100001];
    
   
    
    
    for(int i=0;i<20000000;++i)
    f[i]=1;
    
    f[0]=0;
    f[1]=0;
    
    int m;
    int in;
    int s=0;
    m=(int)sqrt(20000000);
    
    for(int i=2;i*2<20000000;i++)
    f[i*2]=0;
    
    for(int i=3;i<=m;i+=2){
        if(f[i])
        for(int j=3;(j*i)<20000000;j+=2)
        f[j*i]=0;
                       }
                       
                       int ps=1;
       for(int i=3;i<20000000;i+=2){
        if(f[i]&&f[i+2]){
            tp[ps]=i;
            ps++;
            if(ps==100001)
            break;
            }
        }
        
        
        
        while(scanf("%d",&in)!=EOF){
            printf("(%d, %d)\n",tp[in],tp[in]+2);
            }
        
    
    

return 0;
}
 
已經解決
原來測資10000lines
不直接建好twin prime表一定會TLE 
 
ZeroJudge Forum