zj a007 程式執行問題

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

林宇翔

我是用這樣

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