LD送的花。。。# Fashion - 美丽时尚
L*e
1 楼
就是把一个数写成质数相乘，100=2x2x5x5
我写了一个，就是找到所有 小于 n/2 的prime，然后一个一个试。 有啥好的算法吗。
谢谢。
我写了一个，就是找到所有 小于 n/2 的prime，然后一个一个试。 有啥好的算法吗。
谢谢。
s*n
2 楼
今天吃过晚饭，LD一个人跑出去，让我随后跟出去。我忙完，出门就看到恍恍惚惚中，
LD站在一大片草坪中，忙忙叨叨的边走路边往我这边张望。我追上LD后，他露出一个狡
黠的笑容，然后伸出手来，递给我一大把东西（图片在下面），说心情好，给我送花。
。。
唉！人家送花都送玫瑰，郁金香，百合，我咋第一次接到的就是这个东西啊。。。
LD站在一大片草坪中，忙忙叨叨的边走路边往我这边张望。我追上LD后，他露出一个狡
黠的笑容，然后伸出手来，递给我一大把东西（图片在下面），说心情好，给我送花。
。。
唉！人家送花都送玫瑰，郁金香，百合，我咋第一次接到的就是这个东西啊。。。
g*o
3 楼
why n/2?
找小于等于sqrt(n)的prime就可以阿
吗。
【在 L*******e 的大作中提到】
: 就是把一个数写成质数相乘，100=2x2x5x5
: 我写了一个，就是找到所有 小于 n/2 的prime，然后一个一个试。 有啥好的算法吗。
: 谢谢。
找小于等于sqrt(n)的prime就可以阿
吗。
【在 L*******e 的大作中提到】
: 就是把一个数写成质数相乘，100=2x2x5x5
: 我写了一个，就是找到所有 小于 n/2 的prime，然后一个一个试。 有啥好的算法吗。
: 谢谢。
g*n
4 楼
这也太便宜了，罚他三天睡地板吧
L*e
5 楼
sqrt(n) 不够吧，sqrt(10) = 3 while 10 =2 x5
【在 g****o 的大作中提到】
: why n/2?
: 找小于等于sqrt(n)的prime就可以阿
:
: 吗。
【在 g****o 的大作中提到】
: why n/2?
: 找小于等于sqrt(n)的prime就可以阿
:
: 吗。
I*9
6 楼
真浪漫，好幸福～～～
【在 s******n 的大作中提到】
: 今天吃过晚饭，LD一个人跑出去，让我随后跟出去。我忙完，出门就看到恍恍惚惚中，
: LD站在一大片草坪中，忙忙叨叨的边走路边往我这边张望。我追上LD后，他露出一个狡
: 黠的笑容，然后伸出手来，递给我一大把东西（图片在下面），说心情好，给我送花。
: 。。
: 唉！人家送花都送玫瑰，郁金香，百合，我咋第一次接到的就是这个东西啊。。。
【在 s******n 的大作中提到】
: 今天吃过晚饭，LD一个人跑出去，让我随后跟出去。我忙完，出门就看到恍恍惚惚中，
: LD站在一大片草坪中，忙忙叨叨的边走路边往我这边张望。我追上LD后，他露出一个狡
: 黠的笑容，然后伸出手来，递给我一大把东西（图片在下面），说心情好，给我送花。
: 。。
: 唉！人家送花都送玫瑰，郁金香，百合，我咋第一次接到的就是这个东西啊。。。
g*o
7 楼
你把所有小于等于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
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;
}
质数，比如你例子里面的5
如果p[0],p[1],....p[num-1]是所有小于等于sqrt(n)的质数
vector
vector
int i==0;
while(n!=1&&i
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;
}
s*1
8 楼
哈哈，好浪漫啊！绑得很有水平呀！：D
L*e
9 楼
谢谢，学习了！
l*d
10 楼
啊，转送给我吧，我们家gu最爱吃这，哈哈哈！
【在 s******n 的大作中提到】
: 今天吃过晚饭，LD一个人跑出去，让我随后跟出去。我忙完，出门就看到恍恍惚惚中，
: LD站在一大片草坪中，忙忙叨叨的边走路边往我这边张望。我追上LD后，他露出一个狡
: 黠的笑容，然后伸出手来，递给我一大把东西（图片在下面），说心情好，给我送花。
: 。。
: 唉！人家送花都送玫瑰，郁金香，百合，我咋第一次接到的就是这个东西啊。。。
【在 s******n 的大作中提到】
: 今天吃过晚饭，LD一个人跑出去，让我随后跟出去。我忙完，出门就看到恍恍惚惚中，
: LD站在一大片草坪中，忙忙叨叨的边走路边往我这边张望。我追上LD后，他露出一个狡
: 黠的笑容，然后伸出手来，递给我一大把东西（图片在下面），说心情好，给我送花。
: 。。
: 唉！人家送花都送玫瑰，郁金香，百合，我咋第一次接到的就是这个东西啊。。。
m*c
11 楼
请问是如何确定这些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
: while(n%p[i]==0){
: temp++;
我没想明白，谢啦！
【在 g****o 的大作中提到】
: 你把所有小于等于sqrt(n)的质数都试了，如果发现还没被除完，那么剩下的必然是个
: 质数，比如你例子里面的5
: 如果p[0],p[1],....p[num-1]是所有小于等于sqrt(n)的质数
: vector
: vector
: int i==0;
: while(n!=1&&i
: while(n%p[i]==0){
: temp++;
s*n
12 楼
刚开始着实郁闷了一把，可事后来也就想开了，反正总比没有强，我天天喊他臭哄哄的
狗，这正好是极好的印证，哈哈。。。
狗，这正好是极好的印证，哈哈。。。
L*e
13 楼
综合楼上的解答，我试着写了一个。
/**
* 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;
}
/**
* find all the prime up to n(including n)
*/
public static List
List
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
List
// return an empty list
if (n <= 1){
return factors;
}
// all the prime numbers up to sqrt(n)
List
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;
}
s*n
14 楼
刚开始着实郁闷了一把，可事后来也就想开了，反正总比没有强，我天天喊他臭哄哄的
狗，这正好是极好的印证，哈哈。。。
狗，这正好是极好的印证，哈哈。。。
g*o
15 楼
可以有prime factors大于sqrt(n)，但最多只有一个。
试过所有小于等于sqrt(n)的质数，如果n还没被除为1，说明肯定有一个大于sqrt(n）
的质因子
可以看我上面的代码来理解
你以前没接触过数论的话，这里要用到的知识就是；
如果任何一个小于等于sqrt(n)的质数都不能整除n,那么n是个质数
【在 m********c 的大作中提到】
: 请问是如何确定这些prime factors都是小于等于sqrt(n)的？
: 我没想明白，谢啦！
试过所有小于等于sqrt(n)的质数，如果n还没被除为1，说明肯定有一个大于sqrt(n）
的质因子
可以看我上面的代码来理解
你以前没接触过数论的话，这里要用到的知识就是；
如果任何一个小于等于sqrt(n)的质数都不能整除n,那么n是个质数
【在 m********c 的大作中提到】
: 请问是如何确定这些prime factors都是小于等于sqrt(n)的？
: 我没想明白，谢啦！
n*2
16 楼
我LD至今为止送我唯一的一次花是他家地里的棉花
【在 s******n 的大作中提到】
: 今天吃过晚饭，LD一个人跑出去，让我随后跟出去。我忙完，出门就看到恍恍惚惚中，
: LD站在一大片草坪中，忙忙叨叨的边走路边往我这边张望。我追上LD后，他露出一个狡
: 黠的笑容，然后伸出手来，递给我一大把东西（图片在下面），说心情好，给我送花。
: 。。
: 唉！人家送花都送玫瑰，郁金香，百合，我咋第一次接到的就是这个东西啊。。。
【在 s******n 的大作中提到】
: 今天吃过晚饭，LD一个人跑出去，让我随后跟出去。我忙完，出门就看到恍恍惚惚中，
: LD站在一大片草坪中，忙忙叨叨的边走路边往我这边张望。我追上LD后，他露出一个狡
: 黠的笑容，然后伸出手来，递给我一大把东西（图片在下面），说心情好，给我送花。
: 。。
: 唉！人家送花都送玫瑰，郁金香，百合，我咋第一次接到的就是这个东西啊。。。
c*l
17 楼
怎么排除重复解？比如2*3*7和3*2*7
【在 g****o 的大作中提到】
: 可以有prime factors大于sqrt(n)，但最多只有一个。
: 试过所有小于等于sqrt(n)的质数，如果n还没被除为1，说明肯定有一个大于sqrt(n）
: 的质因子
: 可以看我上面的代码来理解
: 你以前没接触过数论的话，这里要用到的知识就是；
: 如果任何一个小于等于sqrt(n)的质数都不能整除n,那么n是个质数
【在 g****o 的大作中提到】
: 可以有prime factors大于sqrt(n)，但最多只有一个。
: 试过所有小于等于sqrt(n)的质数，如果n还没被除为1，说明肯定有一个大于sqrt(n）
: 的质因子
: 可以看我上面的代码来理解
: 你以前没接触过数论的话，这里要用到的知识就是；
: 如果任何一个小于等于sqrt(n)的质数都不能整除n,那么n是个质数
n*y
18 楼
do you think he loves you?
【在 n*******2 的大作中提到】
: 我LD至今为止送我唯一的一次花是他家地里的棉花
【在 n*******2 的大作中提到】
: 我LD至今为止送我唯一的一次花是他家地里的棉花
p*2
19 楼
肯定是从小找到大吧？
【在 c*********l 的大作中提到】
: 怎么排除重复解？比如2*3*7和3*2*7
t*x
20 楼
跑下题，对不住啊lz~~
请问mm养的是小荷兰猪么？
小猪真的最爱吃狗尾草么？我们家的从没给喂过这种，哪天弄点儿来
俺们家的除了吃猪粮，干草，最爱吃的就是生菜啦，呵呵。
【在 l********d 的大作中提到】
: 啊，转送给我吧，我们家gu最爱吃这，哈哈哈！
请问mm养的是小荷兰猪么？
小猪真的最爱吃狗尾草么？我们家的从没给喂过这种，哪天弄点儿来
俺们家的除了吃猪粮，干草，最爱吃的就是生菜啦，呵呵。
【在 l********d 的大作中提到】
: 啊，转送给我吧，我们家gu最爱吃这，哈哈哈！
z*e
21 楼
先从2开始往上除
尽可能多地除以2,直到不行为止
然后找2的下一个prime
3,然后尽量用3去除
如此反复，直到两个数相遇为止
尽可能多地除以2,直到不行为止
然后找2的下一个prime
3,然后尽量用3去除
如此反复，直到两个数相遇为止
t*x
22 楼
lz LD很浪漫啊，呵呵
z*e
23 楼
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一直找下去就可以了
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一直找下去就可以了
d*e
24 楼
很美好.......
B*n
25 楼
试着写一个看看
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;
}
public vector
{
vector
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;
}
A*k
26 楼
可爱的
l*s
27 楼
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;
}
std::vector
{
std::vector
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;
}
t*e
28 楼
俺们家的猪猪爱吃狗尾巴草，蒲公英。。。。西红柿，猕猴桃还有哈密瓜，只要咬住就
不松口
【在 t*x 的大作中提到】
: 跑下题，对不住啊lz~~
: 请问mm养的是小荷兰猪么？
: 小猪真的最爱吃狗尾草么？我们家的从没给喂过这种，哪天弄点儿来
: 俺们家的除了吃猪粮，干草，最爱吃的就是生菜啦，呵呵。
不松口
【在 t*x 的大作中提到】
: 跑下题，对不住啊lz~~
: 请问mm养的是小荷兰猪么？
: 小猪真的最爱吃狗尾草么？我们家的从没给喂过这种，哪天弄点儿来
: 俺们家的除了吃猪粮，干草，最爱吃的就是生菜啦，呵呵。
x*a
29 楼
我的，没考虑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;
}
}
void Find_Prime_Factor(const int& N, vector
{
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;
}
}
E*T
30 楼
这叫有创意～～
r*n
31 楼
这个要比先找到小于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去除
: 如此反复，直到两个数相遇为止
根本不需要找到大于2的质数。
int nextprime(vector
while( true ){
++p;
auto it = primes.begin();
while( p%(*it) ){
it++;
if( it == primes.end() || (*it) * (*it) > p ){
primes.insert(p);
return p;
}
}
}
}
vector
if( N < 0 ) return primefactorizatinon(-N);
vector
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
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去除
: 如此反复，直到两个数相遇为止
l*z
32 楼
嗯，很鲜嫩的创意
【在 E**********T 的大作中提到】
: 这叫有创意～～
【在 E**********T 的大作中提到】
: 这叫有创意～～
相关阅读
如何打造精致的妆容 (转载)打工的人就不可以买名牌？女人穿文胸究竟会不会变美？问一下 有人知道雅诗兰黛的员工折扣是多少么？又到了喝茶美颜的时候啦！无需整容，画出自然高挺小鼻梁床上养生的小妙招大家夏天有没有特别好的配色推荐保持这9个美容习惯，素颜一样美美哒 Zz国女带压舌帽很丑 韩国女和白女带就好看 (转载)夏季穿搭三个常见显高小技巧，来看看你都试过吗？其实女孩子有点肉比较好看日本女人波瑠长得极美 (转载)翡翠与婚纱要如何搭配？最近流行的“三字带”凉鞋踢走四个恶习，瞬间让你白起来 (转载)高级口红真的不沾杯吗？明星自己设计的时尚品牌全都好丑，没本事就别装艺术家了行吗最火的五个去黑眼圈方法 （转载）谁告诉我怎么丰胸啊？拜托