C语言1到N之间的纯素数
时间: 2024-10-10 12:11:16 浏览: 10
在C语言中,判断一个数是否为质数(素数)通常采用埃拉托斯特尼筛法(Sieve of Eratosthenes)或是试除法。以下是简单的思路:
1. **试除法**:对于每个数n,从2开始检查到sqrt(n),如果n能被这个范围内的任何一个数整除,那么n就不是质数。
```c
#include <stdio.h>
int isPrime(int n) {
if (n <= 1) return 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return 0;
}
return 1;
}
void printPrimes(int start, int end) {
for (int i = start; i <= end; i++) {
if (isPrime(i)) printf("%d ", i);
}
}
```
你可以通过`printPrimes(1, N)`来打印1到N之间的所有素数。
**埃拉托斯特尼筛法**则是更高效的方法,适用于找出一定范围内所有素数,而不是单个检查:
```c
#include <stdio.h>
void sieveOfEratosthenes(int limit) {
int prime[limit+1];
memset(prime, 1, sizeof(prime));
prime[0] = prime[1] = 0;
for (int p=2; p*p<=limit; p++) {
// 如果prime[p]没有被改变过,则p是质数
if (prime[p]) {
for (int i=p*2; i<=limit; i += p)
prime[i] = 0;
}
}
for (int p=2; p<=limit; p++)
if (prime[p])
printf("%d ", p);
}
int main() {
int N;
scanf("%d", &N);
sieveOfEratosthanes(N);
return 0;
}
```