购物网站哪个东西便宜质量好,广州网站建设哪家便宜,建设部网站官网挂证通报,河南免费网站建设公司个人主页#xff1a;仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客 专题分栏#xff1a;数论_仍有未知等待探索的博客-CSDN博客 目录 一、暴力求解
1、求1-n之间的素数#xff08;O(n^2)#xff09;
1.思路
2.代码 2、判断某个数x是否为素数
1.思路
2.代码
… 个人主页仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客 专题分栏数论_仍有未知等待探索的博客-CSDN博客 目录 一、暴力求解
1、求1-n之间的素数O(n^2)
1.思路
2.代码 2、判断某个数x是否为素数
1.思路
2.代码
二、 Eratosthenes筛法埃氏筛
1、求1-n之间的素数O(n^logn)
1.思路
2.代码
三、 Euler 筛法欧拉筛法
1、求1-n之间的素数O(n)
1.思路
2.代码 一、暴力求解
在以前的学习的时候我们写过如何求1-n以内的素数也写过判断某个数是否是素数。我们学过素数也称质数只能被1和它本身的整除。
根据这个我们可以开始写了。
1、求1-n之间的素数O(n^2)
1.思路
首先我们要有1-n之间的数然后一个一个的判断其是不是素数然后进行打印。
根据下面的代码或者这个思路我们可以知道这个代码的时间复杂度为O(n^2)。在一些比赛中可能会被卡时间。 因为我们知道1不是素数所以提供的数从2开始。 2.代码
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includemath.h
void _prime(int n);
int main()
{int n;scanf(%d, n);_prime(n);return 0;
}
void _prime(int n)
{//因为我们知道1不是素数所以直接从2开始进行判断for (int i 2; i n; i){//判断是否是素数int flag 0;for (int j 2; j sqrt(i); j){if (i % j 0){flag 1;break;}}if (flag 0){printf(%d , i);}}
} 2、判断某个数x是否为素数
1.思路
循环2-sqrt(x)然后对x进行取余如果取余结果为0则不是素数反之是素数。
2.代码
#includestdio.h
#includemath.h
int isprime(int x);
int main()
{int x;scanf(%d, x);if (isprime(x) 1){printf(YES\n);}else{printf(NO\n);}return 0;
}
int isprime(int x)
{if (x 1)return 0;for (int i 2; i sqrt(x); i){if (x % i 0)return 0;}return 1;
}
二、 Eratosthenes筛法埃氏筛
1、求1-n之间的素数O(n^logn)
1.思路
这个筛法的思路是把所有质数的整数倍全部筛掉。
同样地我们首先是提供1-n之间的数。然后判断数是不是素数如果是素数将素数的整数倍都标记成不是素数。如果不是素数则不做处理。这样的话会减少其时间复杂度但仍然会重复定义。
其时间复杂度是O(n*logn)虽然减少了一点儿可还是有一些长。 判断是不是素数不要写一个判断函数从2-sqrt(n)进行循环取余判断。 我们先设立一个数组用来标记素数。然后我们将数组中全部默认标记为是素数。 然后我们从数字2我们知道数字2是素数开始进行对其整数倍进行标记同理3也是如此。这样就可以将素数进行标记出来。 因为我们知道1不是素数所以提供的数从2开始。 2.代码
#includestdio.h
#define MAX 100
int prime[MAX];//记录素数默认2-n之间全是素数然后再进行筛选
int main()
{int n;scanf(%d, n);for (int i 2; i n; i){//因为我们知道1不是素数所以直接从2开始进行判断if (prime[i] 0){for (int j 2 * i; j n;ji){//0代表素数1代表非素数prime[j] 1;}}}for (int i 2; i n; i){if (prime[i] 0)printf(%d , i);}return 0;
}三、 Euler 筛法欧拉筛法
1、求1-n之间的素数O(n)
1.思路
欧拉筛是唯一筛掉一个数的筛法不存在重复计算所以时间复杂度是O(n)。 核心代码i % prime[j] 0i是素数的倍数。 2.代码
#includestdio.h
#define MAX 100
int prime[MAX];//用来记录素数,0为素数
int record[MAX];
int cnt;//记录素数的大小
void Euler(int n);
int main()
{int n;scanf(%d, n);Euler(n);for (int j 0; j cnt; j){printf(%d , prime[j]);}return 0;
}
void Euler(int n)
{for (int i 2; i n; i){if (!record[i])//如果当前是素数记录下来{prime[cnt] i;}for (int j 0; j cnt i * prime[j] n; j){record[i * prime[j]] 1;if (i % prime[j] 0)break;}}
}
