C语言代码质数筛(埃氏筛))
时间: 2023-07-10 08:41:04 浏览: 52
好的,以下是C语言代码实现质数筛(埃氏筛):
```c
#include <stdio.h>
#define MAX 1000000
int prime[MAX + 1];
void sieve()
{
for(int i = 2; i <= MAX; i++)
{
prime[i] = 1;
}
for(int i = 2; i * i <= MAX; i++)
{
if(prime[i])
{
for(int j = i * i; j <= MAX; j += i)
{
prime[j] = 0;
}
}
}
}
int main()
{
sieve();
for(int i = 2; i <= MAX; i++)
{
if(prime[i])
{
printf("%d ", i);
}
}
return 0;
}
```
该代码使用了埃氏筛法,首先初始化一个数组`prime`,然后将2~MAX之间的数都标记为质数(即`prime[i] = 1`),接着从2开始遍历,将素数的倍数都标记为非质数(即`prime[j] = 0`),最后输出所有标记为质数的数。
希望对你有帮助!
相关问题
c语言埃氏筛法判断素数
以下是使用C语言实现埃氏筛法判断素数的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool is_prime(int n) {
if (n <= 1) {
return false;
}
bool *is_prime = (bool *)malloc(sizeof(bool) * (n + 1));
for (int i = 2; i <= n; i++) {
is_prime[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
bool result = is_prime[n];
free(is_prime);
return result;
}
int main() {
int n = 17;
if (is_prime(n)) {
printf("%d is a prime number.\n", n);
} else {
printf("%d is not a prime number.\n", n);
}
return 0;
}
```
该程序首先判断输入的数是否小于等于1,如果是,则直接返回false,因为1不是素数。然后使用动态数组is_prime来记录每个数是否为素数,初始化时将所有数都标记为素数。接下来从2开始遍历到n,如果当前数是素数,则将其所有倍数都标记为非素数。最后返回is_prime[n]的值,即n是否为素数。
c代码写埃氏筛法求素数
埃氏筛法是一种简单有效的素数筛法,可以用C语言实现。下面是一份参考代码:
```c
#include <stdio.h>
#include <stdlib.h>
void eratosthenes(int n) {
int *is_prime = (int*) malloc(sizeof(int) * (n + 1)); // 为每个数分配一个存储空间
for (int i = 2; i <= n; i++) {
is_prime[i] = 1; // 先假设所有数都是素数
}
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) { // 如果 i 是素数,那么将 i 的倍数标记为非素数
for (int j = i * i; j <= n; j += i) {
is_prime[j] = 0;
}
}
}
printf("2 ");
for (int i = 3; i <= n; i += 2) { // 输出所有素数
if (is_prime[i]) {
printf("%d ", i);
}
}
free(is_prime); // 释放内存空间
}
int main() {
int n;
printf("请输入一个正整数n:");
scanf("%d", &n);
if (n < 2) {
printf("没有素数\n");
return 0;
}
printf("小于等于%d的素数有:\n", n);
eratosthenes(n);
return 0;
}
```
代码中,首先定义了一个动态分配内存的 `is_prime` 数组,用于存储每个数是否为素数。然后初始化所有数都是素数,接着从 2 开始循环,如果当前数是素数,就将其倍数标记为非素数,最后输出剩下的素数。