// https://acm.ecnu.edu.cn/problem/2946/
#include <iostream>
using namespace std;
void getDivides(int n) {
for (int i = 2; i <= n / i; i ++) {
if (n % i == 0) {
int s = 0;
while (n % i == 0) {
n /= i;
s ++;
}
printf("(%d,%d)", i , s);
}
}
if (n > 1) printf("(%d,%d)", n , 1);
puts("");
}
int main() {
int T;
cin >> T;
while (T --) {
int n;
cin >> n;
getDivides(n);
}
return 0;
}
2946. 整数的质因子分解
shwei
aiden
#include <iostream>
#include <vector>
using namespace std;
struct item
{
int p;
int e;
};
bool isPrime(int n)
{
if (n % 2 == 0)
return false;
for (int i = 3; i * i < n; ++i)
{
if (n % i == 0)
return false;
}
return true;
}
int main()
{
vector<int> Prime({ 2 });
for (int i = 3; i < 20000; ++i)
if (isPrime(i))
Prime.push_back(i);
int t;
cin >> t;
while (t--)
{
int a;
cin >> a;
vector<item> vec;
for (auto beg = Prime.begin(); beg != Prime.end(); beg++)
{
if (a % *beg == 0)
{
int cnt = 0;
while (a % *beg == 0)
{
++cnt;
a /= *beg;
}
vec.push_back({ *beg,cnt });
}
else if (a == *beg)
{
vec.push_back({ a, 1 });
break;
}
}
for (const auto &i : vec)
cout << '(' << i.p << "," << i.e << ')';
cout << endl;
}
return 0;
}
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()
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();
}
}
其实不用这么麻烦，比较符合Python风格的思路应该是所有质因数生成列表1，再通过集合为中介去重然后排序保存为列表2，最后用自带的count函数得到列表2内每个元素在列表1中出现的次数
现在最符合Python风格的思路是调用
collections.Counter了（我不确定两年前有没有这个东西可用for example:
最快速度是kangaroo 0.284