判断素数

判断素数

时间: 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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注