2946. 整数的质因子分解

10175102262 LarsPendragon

用python无脑循环会超时!
所以应该先筛一遍再无脑循环……(大概还存在改进空间)

from math import sqrt
T=int(input())
for I in range(T):
    n=int(input())
    count=0
    while n%2 == 0:
        n//=2
        count+=1
    if count:
        print("(2,%d)"%count, end="")
    max=int(sqrt(n))+1
    for i in range(3, max, 2):
        count=0
        while n%i==0:
            n//=i
            count+=1
        if count:
            print("(%d,%d)"%(i, count), end="")
    if n!=1:
        print("(%d,1)"%n, end="")
    print()
10175102262 LarsPendragon

最快速度是kangaroo 0.284

告白于荆州

其实不用这么麻烦,比较符合Python风格的思路应该是所有质因数生成列表1,再通过集合为中介去重然后排序保存为列表2,最后用自带的count函数得到列表2内每个元素在列表1中出现的次数

Li Dao

不用筛素数哦
这里不用筛素数,因为从小到大枚举因数,如果枚举的那个因数不是素数(比如是6),那么,比那个因数的的素因数(2和3)已经把这个数“掏空”了(枚举到6的时候,N%6已经不为0了,因为N已经把2和3全部除完了)

include

using namespace std;
int T,n;

void solve()
{
int N=n;
for(int i=2;i<=n;i++) //不要像我一样从1开始枚举,囧
{
int cnt=0;
if(N%i!=0) continue;
while(N%i==0)
{
N/=i;
cnt++;
}
printf(“(%d,%d)”,i,cnt);
if(N==1) break;
}
cout<>T;
for(int step=0;step>n;
solve();
}
}

你当前正在回复 博客/题目
存在问题!