L*******e
发帖数: 114 | 1 就是把一个数写成质数相乘，100=2x2x5x5
我写了一个，就是找到所有 小于 n/2 的prime，然后一个一个试。 有啥好的算法吗。
谢谢。 |
g****o
发帖数: 547 | 2 why n/2?
找小于等于sqrt(n)的prime就可以阿
吗。
【在 L*******e 的大作中提到】
: 就是把一个数写成质数相乘，100=2x2x5x5
: 我写了一个，就是找到所有 小于 n/2 的prime，然后一个一个试。 有啥好的算法吗。
: 谢谢。
|
L*******e
发帖数: 114 | 3 sqrt(n) 不够吧，sqrt(10) = 3 while 10 =2 x5
【在 g****o 的大作中提到】
: why n/2?
: 找小于等于sqrt(n)的prime就可以阿
:
: 吗。
|
g****o
发帖数: 547 | 4 你把所有小于等于sqrt(n)的质数都试了，如果发现还没被除完，那么剩下的必然是个
质数，比如你例子里面的5
如果p[0],p[1],....p[num-1]是所有小于等于sqrt(n)的质数
vector > factor(int n){
vector > ans;
int i==0;
while(n!=1&&i
int temp=0;
while(n%p[i]==0){
temp++;
n/=p[i];
}
if(temp!=0)ans.push_back(make_pair(p[i],temp));//prime and power
i++;
}
if(n!=1)ans.push_back(make_pair(n,1));
return ans;
} |
L*******e
发帖数: 114 | |
m********c
发帖数: 105 | 6 请问是如何确定这些prime factors都是小于等于sqrt(n)的？
我没想明白，谢啦！
【在 g****o 的大作中提到】
: 你把所有小于等于sqrt(n)的质数都试了，如果发现还没被除完，那么剩下的必然是个
: 质数，比如你例子里面的5
: 如果p[0],p[1],....p[num-1]是所有小于等于sqrt(n)的质数
: vector > factor(int n){
: vector > ans;
: int i==0;
: while(n!=1&&i: int temp=0;
: while(n%p[i]==0){
: temp++;
|
L*******e
发帖数: 114 | 7 综合楼上的解答，我试着写了一个。
/**
* find all the prime up to n(including n)
*/
public static List findPrimes(int n){
List res = new ArrayList();
if (n <= 1) return res;
// create a boolean array to track whether a number
// is a prime or not
boolean[] primeTrack = new boolean[n+1];
for (int i = 2; i <= n; i++){
primeTrack[i] = true;
}
int upper = (int)Math.sqrt(n);
for (int i = 2; i <= upper; i++){
for (int j = i * i; j <= n; j += i){
primeTrack[j] = false;
}
}
for (int i = 2; i <= n; i++){
if (primeTrack[i] == true){
res.add(i);
}
}
return res;
}
public static List primeFactors(int n){
List factors = new ArrayList();
// return an empty list
if (n <= 1){
return factors;
}
// all the prime numbers up to sqrt(n)
List primes = findPrimes((int)Math.sqrt(n));
for (int i : primes){
while ( n % i == 0){
factors.add(i);
n /= i;
}
if (n == 1){
break;
}
}
// the remaining is a prime number, add to the result
if (n > 1){
factors.add(n);
}
return factors;
} |
g****o
发帖数: 547 | 8 可以有prime factors大于sqrt(n)，但最多只有一个。
试过所有小于等于sqrt(n)的质数，如果n还没被除为1，说明肯定有一个大于sqrt(n）
的质因子
可以看我上面的代码来理解
你以前没接触过数论的话，这里要用到的知识就是；
如果任何一个小于等于sqrt(n)的质数都不能整除n,那么n是个质数
【在 m********c 的大作中提到】
: 请问是如何确定这些prime factors都是小于等于sqrt(n)的？
: 我没想明白，谢啦！
|
c*********l
发帖数: 3438 | 9 怎么排除重复解？比如2*3*7和3*2*7
【在 g****o 的大作中提到】
: 可以有prime factors大于sqrt(n)，但最多只有一个。
: 试过所有小于等于sqrt(n)的质数，如果n还没被除为1，说明肯定有一个大于sqrt(n）
: 的质因子
: 可以看我上面的代码来理解
: 你以前没接触过数论的话，这里要用到的知识就是；
: 如果任何一个小于等于sqrt(n)的质数都不能整除n,那么n是个质数
|
p*****2
发帖数: 21240 | 10
肯定是从小找到大吧？
【在 c*********l 的大作中提到】
: 怎么排除重复解？比如2*3*7和3*2*7
|
|
|
z****e
发帖数: 54598 | 11 先从2开始往上除
尽可能多地除以2,直到不行为止
然后找2的下一个prime
3,然后尽量用3去除
如此反复，直到两个数相遇为止 |
z****e
发帖数: 54598 | 12 16
2 - 8
2*2 - 4
2*2*2 - 2
2*2*2*2 -1
52
2 - 26
2*2 - 13
2*2*13 -1
所以压根不用考虑循环的范围
用一个while一直找下去就可以了 |
B********n
发帖数: 384 | 13 试着写一个看看
public vector findPrimes(int n)
{
vector result;
for (int i = 2; i*i <= n; i++)
{
if (n % i == 0)
{
result.push_back(i);
n /= i;
i--;
}
}
result.push_back(n);
return result;
} |
l*****s
发帖数: 774 | 14 steal from others:
std::vector primeFactors(int n)
{
std::vector factors;
if(n<2) return factors;
int d = 2;
while(n>1)
{
while(n%d == 0)
{
factors.push_back(d);
n = n/d;
}
++d;
//optional: stops at the d*d > n
//if(d*d>n)
//{
// factors.push_back(n);
// break;
//}
}
return factors;
} |
x******a
发帖数: 6336 | 15 我的，没考虑N小于等于1.
void Find_Prime_Factor(const int& N, vector& v_prime)
{
if(N==2) v_prime.push_back(N);
int i=2;
while(i<=N){
if(N%i==0){
v_prime.push_back(i);
Find_Prime_Factor(N/i, v_prime);
break;
}
++i;
}
} |
r*********n
发帖数: 4553 | 16 这个要比先找到小于sqrt(N)的所有prime，然后再一个一个除要快。比如输入是2^10，
根本不需要找到大于2的质数。
int nextprime(vector& primes, int p){
while( true ){
++p;
auto it = primes.begin();
while( p%(*it) ){
it++;
if( it == primes.end() || (*it) * (*it) > p ){
primes.insert(p);
return p;
}
}
}
}
vector> primefactorization(int N){
if( N < 0 ) return primefactorizatinon(-N);
vector> ret;
if( N == 0 ){
ret.push_back(make_pair(0,1));
return ret;
}
if( N == 1 ){
ret.push_back(make_pair(1,1));
return ret;
}
vector primes({2});
int p = 2;
while( N != 1 ){
if( p*p > N ){
ret.push_back(make_pair(N,1));
break;
}
int cnt = 0;
while( N%p == 0 ){
++cnt;
N /= p;
}
if( cnt ) ret.push_back(make_pair(p, cnt));
p = nextprime(primes, p);
}
return ret;
}
【在 z****e 的大作中提到】
: 先从2开始往上除
: 尽可能多地除以2,直到不行为止
: 然后找2的下一个prime
: 3,然后尽量用3去除
: 如此反复，直到两个数相遇为止
|
