形成N的非素数对是2个不同的非素数,其中数字的乘积为N。
A non-prime pair which forms N is 2 different non-prime numbers where the product of the numbers is N.
1< = N< = 10 ^ 6
1<=N<=10^6
例如对于N = 24,有2个好对(形成N的非素对)(4,6),( 1,24),但(2,12),(3,8)不好。
For example For N = 24 there are 2 good pairs (non-prime pairs that form N) (4,6), (1,24), but (2,12), (3,8) are not good.
注意:对于任意两个数字a
Note: for any 2 numbers a and b pair(a,b) = pair(b,a).
还有另一个条件指出,如果数字是一个特殊数字,则输出=- 1否则计算非质数。
There is another condition which states that if the number is a special number, so output = -1 otherwise count the number of non-primes.
如果数字可以表示为三个质数的乘积,则称为特殊数。例如:12是一个特殊数字,因为12 = 2 * 2 * 3;
Number is called special number if it can be represented as a product of three prime numbers. Example: 12 is a special number because 12=2*2*3;
我尝试使用 en.wikipedia/wiki/Sieve_of_Eratosthenes ,需要O(N * log (log(N))。
I tried brute-force approach using en.wikipedia/wiki/Sieve_of_Eratosthenes , which takes O(N*log(log(N)).
除了蛮力外,还有没有其他更优化的方法来解决它?
任何想法都会受到赞赏。
Any idea will be appreciated.
预先感谢。
推荐答案首先,Eratosthenes的筛子为O(N * log(log(N))列出所有小于或等于N的素数(当实施得很好)。
First of all, Eratosthenes' sieve is O(N*log(log(N)) to list all primes below or equal N (when well implemented).
第二个:假设您将数量乘以 Q 质数,而没有筛选,最糟糕的是O(sqrt(N))的过程(最糟糕的是,您的数是质数)。您有以下地图:
Second: suppose you factored your number in Q primes with multiplicity which, without sieving, is a process of O(sqrt(N)) at worst (worst: your number is prime). So you have a map of:
- p 0 ->多重性m 0
- p 1 ->多重性m 1
- ...
- p Q ->多重性m Q
- p0 -> multiplicity m0
- p1 -> multiplicity m1
- ...
- pQ -> multiplicity mQ
乘以至少2个素因数可得到多少除数?
How many divisors made from multiplying at least 2 prime factors?
好吧,其中会有 m0 * m1 * ... mq [此处更正]。为什么?好吧,准备一个所有因数的幂产生的所有除数的列表(包括p i 0 == 1),但是将那些因数 1 。
Well, there will be m0*m1*...mq of them [correction here]. Why? Well, prepare a list of all the divisors generated wit the powers of each factor (including pi0==1), but cross out the ones with a power of 1.
- {1, p 0 ,p 0 2 ,... p 0 m0 }是 m0 生成除数的方法具有 p0 的幂,除了p0
- {1, p 1 ,p 1 2 ,... p 1 m1 }是 m1 除
- ...
$ b $之外,具有 p1 次幂的除数的方法b- {1, p Q ,p1 Q ,... p1 mQ }是 mQ 用 pQ
- {1, p0, p02, ...p0m0} are m0 ways of generating divisors with the powers of p0 except p0
- {1, p1, p12, ...p1m1} are m1 ways of generating divisors with the powers of p1 except p1
- ...
- {1, pQ, p1Q, ...p1mQ} are mQ ways of generating divisors with the powers of pQ
具有非质数除数的所有组合的数量(因为每个组中已经包含了 1 且不包括每个质因数)以上所有子集的笛卡尔乘积的基数-因此是各个基数的乘积,因此 m0 * m1 * ... mq
The number of all combinations with non-prime divisors (as 1 is already included in each set and each prime factors by itself is excluded ) will be the cardinality of the cartesian product of all the above subsets - thus the product of the individual cardinalities, therefore 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)); } }更多推荐
计算乘以给定数字N的非素数对的数量,
发布评论