判断素数

判断素数

时间： 1ms        内存：128M

描述：

写一个判断素数的函数，在主函数输入一个整数，输出是否是素数的消息。

输入：

一个数n（n<=1000000007）

输出：

如果是素数输出prime 如果不是输出not prime

示例输入：

97

示例输出：

prime

提示：

参考答案（内存最优[1120]）：

#include<stdio.h>
#define true 1
#define false 0

typedef int bool;


bool is_prime(int n)
{
int divisor;

if(n<=1) return false;
for(divisor=2;divisor*divisor<=n;divisor++)
if(n%divisor==0)
return false;
return true;
}
int main(){
    int flag,n;
    int is_prime(int);   
    scanf("%d",&n);
    flag=is_prime(n);
    if(flag==1)
        printf("prime\n");
    else
        printf("not prime\n");
    return 0;
}

参考答案（时间最优[0]）：

#include<iostream>
#include<cmath>
using namespace std;
int is_prime(int n)
{int i,k,flag=1;
k=sqrt(n);
for(i=2;i<=k&&flag==1;i++)
{if(n%i==0) flag=0;
}
return(flag);
}

int main(){
    int flag,n;
    int is_prime(int);
    cin>>n;
    flag=is_prime(n);
    if(flag==1)
        cout<<"prime"<<endl;
    else
        cout<<"not prime"<<endl;
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。