计算与给定数 N 相乘形成的非素数对的数量，

Question

形成 N 的非素数对是 2 个不同的非素数，其中数字的乘积是 N。

1<=N<=10^6

例如对于N = 24，有2个好的对（形成N的非素数对）（4,6），（1,24），但是（2 ,12), (3,8) 不好。

注意： 对于任意 2 个数字 a 和 b pair(a,b) = pair(b,a)。

还有一个条件是如果这个数是特殊数，那么output = -1 否则统计非素数的个数

能表示为三个素数的乘积的数称为特殊数。示例：12 是一个特殊数字，因为 12=2*2*3;

我尝试使用 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 的蛮力方法，这需要 O(N*log(log(N)).

"Is there any more optimized way to solve it except brute-force?"

任何想法将不胜感激。

提前致谢。

Answer 1

首先，Eratosthenes 的筛法是 O(N*log(log(N)) 列出所有小于或等于 N 的素数（当 well implemented） .

其次：假设你将你的数字分解为 Q 个具有多重性的素数，如果不进行筛选，最坏情况下是 O(sqrt(N)) 的过程（最坏情况：你的数字是素数）。所以你有一张地图：

p₀ -> 多重性 m₀
p₁ -> 多重性 m₁
...
p_Q -> 多重性 m_Q

至少有 2 个质因数相乘得到多少除数？

嗯，会有 m0*m1*...mq [这里更正]。为什么？好吧，准备一个由每个因子的幂生成的所有除数的列表（包括 p_i⁰==1），但是划掉具有 1 次幂的那些。

{1, p₀, p₀², ...p₀^m0} 是 m0 生成除数的方法 p0除了p0
{1, p₁, p₁², ...p₁^m1} 是 m1 生成除数的方法 p1除了p1
...
{1, ~~p_Q~~, p1^Q, ...p1^mQ} 是 mQ 生成具有 pQ

具有非素因数的所有组合的数量（因为 1 已经包含在每个集合中并且每个素因数本身被排除在外）将是上述所有子集的笛卡尔积的基数- 因此是各个基数的乘积，因此 m0*m1*...mq

代码 - Java

import java.util.HashMap;
import java.util.Map;

class Example {

  static void factor(long N, Map<Long, Short> primesWithMultiplicity) {
    // some arg checking and trivial cases
    if(N<0) N=-N;
    if(0==N) {
       throw new IllegalArgumentException(
         "Are you kidding me? Every number divides 0, "+
         "you really want them all listed?"
       );
    }
    if(1==N) {
      primesWithMultiplicity.put(1L,(short)1);
      return;
    }

     // don't try divisors higher than sqrt(N), 
    // if they would have been detected by their composite-complement 
    for(long div=2; div*div < N; ) {
      short multiplicity=0;
      while((N % div)==0) {
        multiplicity++;
        N /= div; // reduce N
      }
      if(multiplicity>0) {
        primesWithMultiplicity.put(div, multiplicity);
      }
      div+= (div == 2 ? 1 : 2); // from 2 to 3, but then going only on odd numbers
    }
    // done.. well almost, if N is prime, then 
    // trying to divide up to sqrt(N) will lead an empty result. But,
    // in this case, N will still be at original value (as opposed 
    // to being 1 if complete factored)
    if(N>1) {
      primesWithMultiplicity.put(N, (short)1);
    }
  }

  static int countDistinctCompositePairs(long N) {
    HashMap<Long, Short> factoringResults=new HashMap<>();
    factor(N, factoringResults);
    int ret=1;
    for(short multiplicity : factoringResults.values()) {
      ret*=multiplicity;
    }
    return ret/2;
  }

  static public void main(String[] args) {
    System.out.println(countDistinctCompositePairs(24));
  }
}

Answer 2

因为你没有提到我假设的限制条件 1<=N<=10^6 实施筛子并同时存储最大 10^6 的数字的最大质因数。

这是相同的代码。

int a[1000001];
a[1]=1;
for(int i=2;i*i<1000001;i++)
{
    if(a[i]==0)
    {
        for(int j=2*i;j<1000001;j+=i)
        a[j]=i;
    }
}

现在如果数字是质数，你的答案是 0。

if(a[n]==0) 
cout<<'0';

如果它是半素数（两个素数的乘积），你的答案就是 1。

if(a[n/a[n]]==0)
cout<<"1";

如果特别的话

int x=n/a[n];
if(a[x/a[x]]==0)
cout<<"-1";

如果不满足上述任何条件，则计算所有非素因数。

int c=0;
for(int i=1;i*i<n;i++)
    {
        if(n%i==0)
        {
            if(a[i]!=0&&a[n/i]!=0)
            c++;

        }
    }

希望对您有所帮助！

计算与给定数 N 相乘形成的非素数对的数量，

Count number of non-prime pairs that when multiplied form a given number N,

java

arrays

algorithm

primes

time-complexity