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;
}

}

林宇翔

我是用這樣

[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;
}

allenwhale

這題直接做也可以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[i]*p[i]<=N;i++)
		{
			if(N%p[i]==0)
			{
				printf("非質數\n");
				goto end;
			}
		}
		printf("質數\n");
		end:;
	}
	return 0;
}

Sylveon

AC 這一題的方法

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

visitorIKC

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

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

Brad

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

Sylveon

我記得營隊的時後有叫大家先不要寫a007

allenwhale

這已經不是TLE的問題吧
會先RE吧

visitorIKC

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

Panda_Liu

break呢？ 大大？