[数据结构与算法]洛谷题解 U170049 [number_theory2]Prime

题目传送门

此题的本质是显而易见的,即使用尽量快的方法判断一数是否为素数,在代码量较小的方法中,以下三种类型较为主流

第一部分 判断素数

第一种方法:思想即遍历所有满足n∈[2,x]的正整数,检查x是否能整除n,如果能,则返回0,否则返回1,时间复杂度为O(n),故有代码如下

?bool is_Prime(int x){
    for(int i=2;i<=x;i++){ //遍历2到x
        if(x%i==0) return 0; //若能被n整除,则返回0
    }
    return 1; //否则返回1
}

第二种方法:思想即遍历所有满足n∈[2,√x]的正整数,检查x是否能整除n,如果能,则返回0,否则返回1,即题干中介绍的方法,时间复杂度为O(√n),故有代码如下

?bool is_Prime(int x){
    for(int i=2;i<=sqrt(x);i++){ //遍历2到sqrt(x)
        if(x%i==0) return 0; //若能被n整除,则返回0
    }
    return 1; //否则返回1
}

第三种方法:因为有2,3为素数,则在大于3的正整数n中:

• 若 n%6==0或n%6==2或n%6==4 则n能被2整除,n不为素数
• 若 n%6==3 则n能被3整除,n不为素数

即 n%6==1或n%6==5是n为素数的必要非充分条件,故有代码如下

bool is_Prime(int x){
    if(x==2||x==3) return 1; //如果x为2或3,则返回1
    if(!(x%6==1||x%6==5)) return 0; //如果x%6不为1或5,则返回0
    for(int i=5;i<=sqrt(x);i+=6){ //遍历6到sqrt(x)中6的倍数-1 (减1为了保证边界判断) 
        if(x%i==0||x%(i+2)==0) return 0; //若x能被i或i+2整除,则返回0
    }
    return 1; //否则返回1
}

?本题的时间限制是200ms,较为严格,故只能使用此种方法

第二部分 输入与排错

本题的输入很简单,即一个32位整型变量(使用64位整形变量会加大运算负担,不能通过),而字符串输入不会改变整型变量的值,故可先定义x为不合法输入,若输入后x仍不合法,则输入不合法

int x=0; //定义32位整型变量x,因为合法输入为正整数,故初始值不定义为正整数
scanf("%d",&x); //输入x
if(x==0){ //如果x的值未被更改,则为不合法输入
    for(int i=1;i<=5;i++) printf("Test Error.\n"); //排错
    return 0; //提前终止程序
}

第三部分 任务处理

任务一,可直接调用写好的 is_Prime 函数输出,代码如下

void task1(int x){
    if(is_Prime(x)) printf("true\n"); //若为素数,则输出"true"
    else printf("false\n"); //否则输出"false"
}

任务二,遍历2到x中的所有数,并用 is_Prime 函数输出,代码如下

void task2(int x){
    for(int i=2;i<x;i++){ //遍历2到x-1
        if(is_Prime(x)) printf("%d ",i); //若为素数,则按格式输出
    }
    printf("\n"); //提行
}

任务三,遍历2到x中的所有数,并用 is_Prime 函数输出,代码如下

void task3(int x){
    for(int i=2;i<x;i++){ //遍历2到x
        if(!is_Prime(x)) printf("%d ",i); //若不为素数,则按格式输出
    }
    printf("\n"); //提行
}

任务四,遍历比x大的所有数,并用 is_Prime 函数输出,遇到素数则停止,代码如下

void task4(int x){
    for(int i=x+1;;i++){ //遍历比x大的数
        if(is_Prime(i)){
            printf("%d\n",i); //若为素数,则按格式输出
            return; //终止函数
        }
    }
}

任务五,若x为奇数,则x+1为偶数,输出x+1,若x为偶数,则若x+1不为素数,输出x+1,否则输出x+2

void task5(int x){
    if(x%2==1){ //如果x为奇数
        printf("%d\n",x+1); //输出x+1
        return; //提前终止函数
    }
    if(!is_Prime(x+1)){ //如果x+1不为素数
        printf("%d\n",x+1); //输出x+1
        return; //提前终止函数
    }
    printf("%d\n",x+2); //输出x+2
}

第四部分 AC代码

#include<cstdio>
#include<cmath>
using namespace std;

bool is_Prime(int x){
    if(x==2||x==3) return 1; //如果x为2或3,则返回1
    if(!(x%6==1||x%6==5)) return 0; //如果x%6不为1或5,则返回0
    int p=sqrt(x); //保存sqrt(x)的值,避免多次计算 
    for(int i=5;i<=p;i+=6){ //遍历6到sqrt(x)中6的倍数-1 (减1为了保证边界判断) 
        if(x%i==0||x%(i+2)==0) return 0; //若x能被i-1或i+1整除,则返回0
    }
    return 1; //否则返回1
}

void task1(int x){
    if(is_Prime(x)) printf("true\n"); //若为素数,则输出"true"
    else printf("false\n"); //否则输出"false"
}

void task2(int x){
    for(int i=2;i<x;i++){ //遍历2到x
        if(is_Prime(i)) printf("%d ",i); //若为素数,则按格式输出
    }
    printf("\n"); //提行
}

void task3(int x){
    for(int i=2;i<x;i++){ //遍历2到x
        if(!is_Prime(i)) printf("%d ",i); //若不为素数,则按格式输出
    }
    printf("\n"); //提行
}

void task4(int x){
    for(int i=x+1;;i++){ //遍历比x大的数
        if(is_Prime(i)){
            printf("%d\n",i); //若为素数,则按格式输出
            return; //终止函数
        }
    }
}

void task5(int x){
    if(x%2==1){ //如果x为奇数
        printf("%d\n",x+1); //输出x+1
        return; //提前终止函数
    }
    if(!is_Prime(x+1)){ //如果x+1不为素数
        printf("%d\n",x+1); //输出x+1
        return; //提前终止函数
    }
    printf("%d\n",x+2); //输出x+2 
}

int main(){
	int x=0; //定义32位整型变量x,因为合法输入为正整数,故初始值不定义为正整数
	scanf("%d",&x); //输入x
	if(x==0){ //如果x的值未被更改,则为不合法输入
 	   for(int i=1;i<=5;i++) printf("Test Error.\n"); //排错
 	   return 0; //提前终止程序
	}
	task1(x);
	task2(x);
	task3(x);
	task4(x);
	task5(x);
	return 0;
}