形成 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))。
“除了暴力破解,还有什么更优化的解决方法吗?”
任何想法将不胜感激。
提前致谢。
最佳答案
首先,Eratosthenes 的筛法是 O(N*log(log(N)) 列出所有小于或等于 N 的素数(当 well implemented 时)。
第二:假设您将您的数字分解为具有多重性的 Q
素数,如果不进行筛选,最坏情况下是 O(sqrt(N)) 的过程(最坏情况:您的数字是素数)。所以你有一张 map :
- p0 -> 多重性 m0
- p1 -> 多重性 m1
- ...
- pQ -> 多重性 mQ
有多少个因数乘以至少 2 个质因数?
好吧,它们会有 m0*m1*...mq
[此处更正]。为什么?好吧,准备一个由每个因数(包括 pi0==1)的幂生成的所有除数的列表,但划掉幂为 1
。
- {1,
p0, p02, ...p0m0} 是m0
生成除数的方法,具有p0
除了 p0 的幂
- {1,
p1, p12, ...p1m1} 是m1
生成除数的方法,具有p1
除了 p1 的幂
- ...
- {1,
pQ, p1Q, ...p1mQ} 是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));
}
}
关于java - 计算与给定数 N 相乘形成的非素数对的数量,,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40692681/