寻找最小素数x和最大m = power_of（x）的函数，使得n％m = 0且n％x = 0？

Question

给出从1到m的m个整数，对于每个1 <= i <= m求出i % x = 0的最小素数x和是x的幂的最大数y，以使i % y = 0

我的主要方法是：我使用Eratos agorithm来查找每个m的x，如下所示：我使用set可以更方便地跟踪

#include<bits/stdc++.h>
using namespace std;
set<int> s;
void Eratos() {
    while(!s.empty()) {
        int prime = *s.begin();
        s.erase(prime);
        X[prime] = prime;
        for(int j = prime * 2; j <= L ; j++) {
            if(s.count(j)) {
                  int P = j / prime;
                  if( P % prime == 0) Y[j] =  Y[P]*prime;
                  else Y[j] = prime;
            }
        }
    }
signed main() {
     for(int i = 2; i<= m; i++) s.insert(i);
     Eratos();
     for(int i = 1; i <= m; i++) cout << X[m] << " " << Y[m] ;
 }

[X[m]是与m对应且与Y[m]相同的数字x但这似乎并不是真正快速，最佳的解决方案。对此的内存请求非常大，当m为1000000时，我得到了MLE。因此请提供一个可以帮助解决此问题的功能。非常感谢。

Answer 1

而不是简单地在Eratosthenes的原始筛网中标记数字质数/非质数，请保存相应的最小质数因子，该因数除以该数字。一旦完成，一个数的最小素数的最大功效就是简单地检查最小的素数在该数的素因式分解中出现了多少次，这是嵌套的for循环在以下代码中所做的事情：

#include <iostream>
#include <vector>

using namespace std;

void SoE(vector<int>& sieve)
{
    for (int i = 2; i < sieve.size(); i += 2)
        sieve[i] = 2;
    for (int i = 3; i < sieve.size(); i += 2)
        if (sieve[i] == 0)
            for (int j = i; j < sieve.size(); j += i)
                if(sieve[j] == 0)
                    sieve[j] = i;
}

int main()
{
    int m;
    cin >> m;

    vector<int> sieve(m + 1, 0);
    SoE(sieve);

    for (int i = 2; i < sieve.size(); ++i)
    {
        int x, y;

        x = y = sieve[i];
        for (int j = i; sieve[j / x] == x; j /= x)
            y *= x;
        cout << x << ' ' << y << endl;
    }
}

Answer 2

我没有得到您要执行的操作，但是我了解到您正在尝试使用Eratosthenes的Sieve来查找素数。好吧，您可能需要一个位集，它就像一个布尔数组，但是使用位而不是字节，这意味着它使用的内存更少。这是我所做的：

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

vector<int> primes;

int main()
{
    const int m = 1e7;
    bitset<m> bs;

    int limit = (int) sqrt (m);
    for (int i = 2; i < limit; i++) {
        if (!bs[i]) {
            for (int j = i * i; j < m; j += i)
                bs[j] = 1;
        }
    }

    for (int i = 2; i < m; i++) {
        if (!bs[i]) {
            primes.push_back (i);
        }
    }

    return 0;
}