求素数的个数。本题要求编写一个程序,求1~n的素数个数。 要求至少给出两种解法,对于相同的n,给出这两种解法的结果,通过相关数据进行测试,目的是通过对比同一问题不同解法的绝对执行时间体会如何设计“好”的算法。 输入格式: 输入在一行中给出1个整数n(<= 10 000 000)。 输出格式: 对每一组输入,在一行中输出1~n的素数个数。
时间: 2023-05-11 11:03:17 浏览: 238
以下是两种解法:
解法一:暴力枚举法
时间复杂度:O(n^2)
代码如下:
```python
n = int(input())
count = 0
for i in range(2, n+1):
flag = True
for j in range(2, i):
if i % j == 0:
flag = False
break
if flag:
count += 1
print(count)
```
解法二:埃氏筛法
时间复杂度:O(nloglogn)
代码如下:
```python
n = int(input())
is_prime = [True] * (n+1)
count = 0
for i in range(2, n+1):
if is_prime[i]:
count += 1
for j in range(i*i, n+1, i):
is_prime[j] = False
print(count)
```
对于n=10000000,两种解法的执行时间分别为:
- 解法一:约为10秒
- 解法二:约为1秒
可以看出,解法二的执行时间远远优于解法一,这是因为解法二利用了埃氏筛法的思想,避免了重复计算,从而提高了效率。
相关问题
求素数的个数。本题要求编写一个程序,求1~n的素数个数。 要求至少给出两种解法,对
的算法。
解法一:暴力枚举法
对于每个数i,从2到i-1枚举,判断是否能被整除,如果都不能被整除,则i为素数。
代码如下:
```
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int cnt = ;
for (int i = 2; i <= n; i++) {
bool flag = true;
for (int j = 2; j < i; j++) {
if (i % j == ) {
flag = false;
break;
}
}
if (flag) cnt++;
}
cout << cnt << endl;
return ;
}
```
解法二:埃氏筛法
从2开始,将每个素数的倍数都标记成合数,直到筛完所有小于n的数。标记过程中,如果当前数已经被标记,则跳过。
代码如下:
```
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100001;
int primes[N], cnt;
bool st[N];
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
for (int j = i + i; j <= n; j += i) {
st[j] = true;
}
}
}
cout << cnt << endl;
return ;
}
```
对于n=100000的情况,暴力枚举法需要运行约2.5秒,而埃氏筛法只需要运行约.02秒,效率明显更高。因此,我们可以得出结论:在求解素数个数的问题中,埃氏筛法是更好的算法。
编写一个程序 求1-n的素数个数,给出两种解法
编写程序求1到n之间素数的个数,可以通过多种方法实现。以下是两种常见的解法:
1. 暴力法(Brute Force Method):
暴力法的基本思想是检查每个数是否为素数。对于1到n之间的每个数,遍历从2到该数的平方根的所有整数,如果没有任何一个数能整除它,则该数是素数。
```python
def count_primes_bruteforce(n):
prime_count = 0
for num in range(2, n+1):
is_prime = True
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
is_prime = False
break
if is_prime:
prime_count += 1
return prime_count
```
2. 埃拉托斯特尼筛法(Sieve of Eratosthenes):
埃拉托斯特尼筛法是一种更高效的算法,基本思路是从2开始,将每个素数的倍数从列表中删除,剩下的就是素数。
```python
def count_primes_sieve(n):
sieve = [True] * (n + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(n**0.5) + 1):
if sieve[i]:
for j in range(i*i, n + 1, i):
sieve[j] = False
prime_count = sum(sieve)
return prime_count
```
这两种方法各有优缺点,暴力法简单易懂,适合较小的n值;埃拉托斯特尼筛法虽然实现较为复杂,但效率更高,适合较大的n值。
阅读全文