竹園論壇

標題: zj a007 程式執行問題 [打印本頁]

---

作者: 林宇翔    時間: 2014-8-26 12:49
標題: zj a007 程式執行問題
每次執行此程式都出現這個
程式碼如下

[C++] 純文本查看 復制代碼

#include<iostream>

#include<iostream>

using namespace std;

int main()

{

        int x;

        while(cin>>x)

        {

                for(int e=0;e<=x;e++)

                {

                        if(x%e != 1)

                        {

                                cout<<"非質數"<<endl;

                        }

                        

                }

                cout<<"質數"<<endl;

                

        

        }

        

        return 0;

}



}

1.png (83.08 KB, 下載次數: 36)

下載附件

2014-8-26 13:19 上傳

---

作者: allenwhale    時間: 2014-8-26 13:58
因為你每次都有x%0出現
不RE才奇怪

---

作者: Brad    時間: 2014-8-26 18:10
這樣算對於所有數字應該都會輸出 非質數 吧
而且可能不只輸出一次
然後輸出 非質數 後再輸出 質數

---

作者: Panda_Liu    時間: 2014-8-26 18:47
break呢？ 大大？

---

作者: visitorIKC    時間: 2014-8-26 19:14


你的演算法有接近100%的機率得到可愛的TLE...(ZJ a007)

---

作者: allenwhale    時間: 2014-8-26 19:16
這已經不是TLE的問題吧
會先RE吧

---

作者: Sylveon    時間: 2014-8-26 19:34
我記得營隊的時後有叫大家先不要寫a007

---

作者: Brad    時間: 2014-8-26 20:40


我幫你試過了
這種方式會 TLE
e<=sqrt(x) 也一樣
先判斷x是否為2的倍數,若非則e再把小於等於sqrt(x)的奇數都跑一次也一樣

---

作者: visitorIKC    時間: 2014-8-26 21:20

Brad 發表於 2014-8-26 20:40
我幫你試過了
這種方式會 TLE
e

判斷2,3,6n+1,6n+5,e<=sqrt(x)也一樣
就是因為這樣這題到現在我還沒有AC.

---

作者: Sylveon    時間: 2014-8-26 21:31
AC 這一題的方法

1.雞尾酒方法(我亂取的)
2.範圍內100%正確的隨機演算法

---

作者: allenwhale    時間: 2014-8-26 22:01
這題直接做也可以AC吧

[C++] 純文本查看 復制代碼

#include <stdio.h>

int p[7000];

int pn=0;

void init()

{

        p[pn++]=2;

        p[pn++]=3;

        for(int i=5;i<=65536;i+=2)

        {

                bool tf=true;

                for(int j=0;j<pn&&p[j]*p[j]<=i;j++)

                {

                        if(i%p[j]==0)

                        {

                                tf=false;

                                break;

                        }

                }

                if(tf)p[pn++]=i;

        }

}

int main()

{

        init();

        int N;

        while(~scanf("%d",&N))

        {

                for(int i=0;i<pn&&p*p<=N;i++)

                {

                        if(N%p==0)

                        {

                                printf("非質數\n");

                                goto end;

                        }

                }

                printf("質數\n");

                end:;

        }

        return 0;

}

---

作者: 林宇翔    時間: 2014-8-27 12:57
我是用這樣

[C++] 純文本查看 復制代碼

#include<iostream>

using namespace std;

int main()

{

        bool IsPrime[1000001];

    IsPrime[0] = 0;

    IsPrime[1] = 0;

    for(int m=2;m<1000001;m++)

        IsPrime[m] = 1;

        

    for(int m=4;m<1000001;m+=2)

        IsPrime[m] = 0;

    for(int m=3;m<1000001;m+=2)

    {

        if(IsPrime[m])

            for(int n=m*2;n<1000001;n+=m)

                IsPrime[n] = 0;

    }

    

    int a,ans;

    while(cin>>a)

    {

        if(IsPrime[a] == 1)

        {

                cout<<"質數"<<endl; 

        }

        else

        {

                cout<<"非質數"<<endl;

        }

    }

        return 0;

}

---

歡迎光臨 竹園論壇 (http://forum.tfcis.org/)

Powered by Discuz! X3.2