天秀洛谷专题 - 素数筛

素数筛

Almost Prime

Almost Prime

#include<bits/stdc++.h>
using namespace std;

const int N = 3000;
vector<bool> is_prime(N+1, true);
vector<int> primes;

// 线性筛生成所有小于N的质数
void sieve() {
    is_prime[0] = is_prime[1] = false; // 0和1不是质数
    for (int i = 2; i <= N; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = 2*i; j <= N; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int countAlmostPrimes(int n) {
    sieve(); // 生成质数
    int count = 0;
    
    for (int i = 1; i <= n; ++i) {
        int temp = i;
        int distinctPrimeFactors = 0;
        
        // 计算i的不同质因子数量
        for (int j = 0; j < primes.size() && primes[j] * primes[j] <= temp; ++j) {
            if (temp % primes[j] == 0) {
                distinctPrimeFactors++;
                while (temp % primes[j] == 0) temp /= primes[j];
            }
        }
        if (temp > 1) distinctPrimeFactors++; // 处理剩余的大于sqrt(i)的质因子
        
        if (distinctPrimeFactors == 2) count++; // 如果恰好有两个不同的质因子
    }
    
    return count;
}

int main() {
    int n;
    cin >> n;
    cout << countAlmostPrimes(n) << endl;
    return 0;
}

if (temp > 1) distinctPrimeFactors++; // 处理剩余的大于sqrt(i)的质因子

这句代码的作用是处理那些在遍历质数并尝试除以它们时剩余的、未被完全除尽的质因子。具体来说，在检查一个数i的质因子时，通常的做法是遍历小于等于sqrt(i)的所有质数，因为一个合数必有一个不大于它的平方根的质因子。

在这个过程中，对于每一个遍历到的质数p，如果i可以被p整除，我们就把i除以p，直到i不能再被p整除。这样做的目的是找出i的所有质因子，并计算它有多少个不同的质因子。

但是，在遍历完所有小于等于sqrt(i)的质数后，可能还剩下一个大于sqrt(i)的质因子。例如，假设i = 2 * 7 * 13，当我们遍历到7并除以7之后，剩下的数是13，它大于sqrt(i)。在这种情况下，我们需要增加distinctPrimeFactors的计数，以确保计算的质因子数量是正确的。

这句话的逻辑是：

• 如果在完成上述遍历后temp大于1，这意味着i除以它的所有小于等于sqrt(i)的质因子后，还剩下一个大于sqrt(i)的质因子。这个剩余的temp本身就是一个质因子，因为如果它是合数，它就会在之前的遍历中被除尽。
• 因此，我们需要把这个剩余的质因子计入总的不同质因子数量中，即通过distinctPrimeFactors++来实现。

这个步骤对于确保当一个数具有大于sqrt(i)的质因子时能够正确计算其质因子总数是必需的。

[ARC017A] 素数、コンテスト、素数

[ARC017A] 素数、コンテスト、素数

//日本题目记得答案要输出换行
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
vector<bool> is_primes(N+1,true);
vector<int> primes;

void linesieve(){
	is_primes[0] = is_primes[1] = false;
	for(int i=2; i<=N; i++){
		if(is_primes[i]){
			primes.push_back(i);
		}
		for(int j=0; j < primes.size() && i * primes[j] <= N; ++j){
			is_primes[i * primes[j]] = false;
			if(i % primes[j] == 0) break;
		}
	}
}
bool isprime(int n){
	if(n<=1) return false;
	for(int i=2; i * i <=n; i++){
		if(n % i == 0){
			return false;
		}
	}
	return true;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	linesieve();
	if(is_primes[n]){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}

}

[ARC044A] 素数判定

[ARC044A] 素数判定

超时代码展示：

#include<bits/stdc++.h>
using namespace std;
bool is_Prime(int n){
	if(n==1) return false;
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0) return false;
	}
	return true;
}
bool is_HuiWen(int n){
	string s=to_string(n);
	int len=s.size();
	for(int i=0;i<len/2;i++){
		if(s[i]!=s[len-i-1]) return false;
	}
	return true;
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int l,r;
	cin>>l>>r;
	for(int i=l;i<=r;i++){
		if(is_HuiWen(i)&&is_Prime(i)){
			cout<<i<<endl;
		}
	}
	return 0;
}

要分析这段代码的时间复杂度，我们需要逐个看每个函数和主循环。

1. is_Prime 函数: 这个函数检查一个数是否为质数。它做了一个从2遍历到sqrt(n)的循环。因此，is_Prime函数的时间复杂度为O(sqrt(n))。

2. is_HuiWen 函数: 这个函数检查一个数n是否为回文数。它首先转换这个数为字符串，然后检查字符串是否为回文。由于字符串的长度是数字n的位数D（D = log10(n)），这个函数的循环会运行D/2次。因此，is_HuiWen函数的时间复杂度为O(D) = O(log(n))。

3. 主循环: 主循环遍历从l到r的所有数，对每个数i调用is_HuiWen和is_Prime函数。如果r-l=N，那么主循环将执行N次。因此，主循环的时间复杂度是N乘以这两个函数时间复杂度的和。

综上所述，主循环的时间复杂度为O(N * (sqrt(n) + log(n)))。因为sqrt(n)在大数范围内增长速度快于log(n)，所以整体时间复杂度主要受sqrt(n)的影响，我们可以近似表示为O(N*sqrt(n))。

然而，这里的n是循环中的当前数字i，它在l到r之间变化。如果我们考虑最坏情况（即r是最大值），整体时间复杂度可以进一步概括为O(N*sqrt®)。这里的N是数字的范围（r-l+1），r是范围内的最大值。

正确思路展示

为了解决这个问题，我们可以使用线性筛（也称为埃拉托斯特尼筛法的优化版本）来高效地生成范围内的所有质数，然后从这些质数中筛选出回文数。线性筛的好处在于它对每个合数只进行一次筛选，时间复杂度为O(n)，这使得它非常适合用于处理大范围内的质数筛选问题。

接下来，我们按照以下步骤进行：

1. 使用线性筛生成小于或等于一亿的所有质数。
2. 遍历这些质数，检查它们是否是回文数。
3. 如果一个质数是回文数，且在给定的区间内，则输出这个数。

线性筛法改进代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100000000;
vector<int> primes;
vector<bool> prime(MAXN + 1, true);

void linearSieve() {
    prime[0] = prime[1] = false;
    for (int i = 2; i <= MAXN; i++) {
        if (prime[i]) {
            primes.push_back(i);
        }
        for (size_t j = 0; j < primes.size() && i * primes[j] <= MAXN; j++) {
            prime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
}

bool isPalindrome(int n) {
    string s = to_string(n);
    string rev_s = s;
    reverse(rev_s.begin(), rev_s.end());
    return s == rev_s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int a, b;
    cin >> a >> b;
    linearSieve();

    for (int i = 0; i < primes.size() && primes[i] <= b; i++) {
        if (primes[i] >= a && isPalindrome(primes[i])) {
            cout << primes[i] << endl;
        }
    }

    return 0;
}

这段代码首先利用线性筛法预先计算并存储所有小于等于一亿的质数，然后通过简单地遍历这些质数并检查它们是否为回文数来解决原问题。

由于这种方法预计算了所有需要的质数，它能显著减少在给定区间内检查每个数是否为质数的需要，特别是对于大范围数据来说，这种方法能大幅提高效率。