将 PARI 程序转换为 C++
Convert PARI program to C++
我在 OEIS 中找到了一个 sequence of interest,我想在 C++ 中为我正在研究的编程竞赛解决方案生成相同的序列。
但是我在理解序列页面中给出的程序如何工作时遇到了障碍。
这是页面中给出的程序 -
(PARI) test(n)= {m=n; forprime(p=2, 5, while(m%p==0, m=m/p));
return(m==1)} for(n=1, 500, if(test(n), print1(n", ")))
(PARI) a(n)=local(m); if(n<1, 0, n=a(n-1);
until(if(m=n, forprime(p=2, 5, while(m%p==0, m/=p)); m==1), n++); n)
(PARI) list(lim)={
lim\=1;
my(v=List(), s, t);
for(i=0, log(lim+.5)\log(5),
t=5^i;
for(j=0, log(lim\t+.5)\log(3),
s=t*3^j;
while(s <= lim,
listput(v, s);
s <<= 1;
)
)
);
vecsort(Vec(v))
};
我知道了 PARI 是什么,但我无法将此程序转换为 C++。任何帮助我在 C++ 中生成相同序列的建议将不胜感激。
我尝试使用以下代码片段在 C++ 中生成序列。但我想我错过了中间的某些数字,因为我在网上 IDE.
中的一些测试失败了
for(int i = 0; i < 16; i++)
{
for(int j = 0; j < 15; j++)
{
for(int k = 0; k < 12; k++)
{
std::cout<<pow(2,i)*pow(3,j)*pow(5,k)<<std::endl;
}
}
}
我选择 16、15 和 12 作为限制,否则结果值会溢出 long 变量类型。
这里有三个程序,每个程序都有不同的用途。
第一个检查数字是否是 5 平滑的。它简单地除以 2、3 和 5,直到不能再除,然后测试剩下的是否为 1。
第二个生成第“'n'”个 5 平滑数。它使用与第一个相同的想法,测试范围内的每个数字。这是非常低效的!
第三个生成达到给定界限的所有 5 平滑数。
我假设第三个是您想要的,因为它似乎最适合您的情况。 (这也有助于我是该程序的作者。)
#include <iostream>
#include <vector>
#include <algorithm>
int main(void);
std::vector<long> smooth(long lim);
int main(void) {
long lim = 1000;
std::vector<long> v = smooth(lim);
std::cout << "5-smooth numbers up to " << lim << ": ";
for (std::vector<long>::iterator it = v.begin(); it != v.end(); it++) {
std::cout << *it << ", ";
}
std::cout << "\n";
return 0;
}
std::vector<long> smooth(long lim) {
std::vector<long> v = {};
for (long t = 1; t <= lim; t*=5) {
for (long s = t; s <= lim; s*=3) {
for (long n = s; n <= lim; n*=2) {
v.push_back(n);
}
}
}
std::sort(v.begin(), v.end());
return v;
}
当然,这不是逐行转换;例如,我没有使用对数,因为精确对数不像 PARI 那样内置于 C++ 中。它非常快,它在几分之一秒内找到所有 5-smooth 数字,最大为 1,844,674,407,370,955,161(它在 64 位机器上可以做的最大数字)。
我在 OEIS 中找到了一个 sequence of interest,我想在 C++ 中为我正在研究的编程竞赛解决方案生成相同的序列。
但是我在理解序列页面中给出的程序如何工作时遇到了障碍。
这是页面中给出的程序 -
(PARI) test(n)= {m=n; forprime(p=2, 5, while(m%p==0, m=m/p));
return(m==1)} for(n=1, 500, if(test(n), print1(n", ")))
(PARI) a(n)=local(m); if(n<1, 0, n=a(n-1);
until(if(m=n, forprime(p=2, 5, while(m%p==0, m/=p)); m==1), n++); n)
(PARI) list(lim)={
lim\=1;
my(v=List(), s, t);
for(i=0, log(lim+.5)\log(5),
t=5^i;
for(j=0, log(lim\t+.5)\log(3),
s=t*3^j;
while(s <= lim,
listput(v, s);
s <<= 1;
)
)
);
vecsort(Vec(v))
};
我知道了 PARI 是什么,但我无法将此程序转换为 C++。任何帮助我在 C++ 中生成相同序列的建议将不胜感激。
我尝试使用以下代码片段在 C++ 中生成序列。但我想我错过了中间的某些数字,因为我在网上 IDE.
中的一些测试失败了for(int i = 0; i < 16; i++)
{
for(int j = 0; j < 15; j++)
{
for(int k = 0; k < 12; k++)
{
std::cout<<pow(2,i)*pow(3,j)*pow(5,k)<<std::endl;
}
}
}
我选择 16、15 和 12 作为限制,否则结果值会溢出 long 变量类型。
这里有三个程序,每个程序都有不同的用途。
第一个检查数字是否是 5 平滑的。它简单地除以 2、3 和 5,直到不能再除,然后测试剩下的是否为 1。
第二个生成第“'n'”个 5 平滑数。它使用与第一个相同的想法,测试范围内的每个数字。这是非常低效的!
第三个生成达到给定界限的所有 5 平滑数。
我假设第三个是您想要的,因为它似乎最适合您的情况。 (这也有助于我是该程序的作者。)
#include <iostream>
#include <vector>
#include <algorithm>
int main(void);
std::vector<long> smooth(long lim);
int main(void) {
long lim = 1000;
std::vector<long> v = smooth(lim);
std::cout << "5-smooth numbers up to " << lim << ": ";
for (std::vector<long>::iterator it = v.begin(); it != v.end(); it++) {
std::cout << *it << ", ";
}
std::cout << "\n";
return 0;
}
std::vector<long> smooth(long lim) {
std::vector<long> v = {};
for (long t = 1; t <= lim; t*=5) {
for (long s = t; s <= lim; s*=3) {
for (long n = s; n <= lim; n*=2) {
v.push_back(n);
}
}
}
std::sort(v.begin(), v.end());
return v;
}
当然,这不是逐行转换;例如,我没有使用对数,因为精确对数不像 PARI 那样内置于 C++ 中。它非常快,它在几分之一秒内找到所有 5-smooth 数字,最大为 1,844,674,407,370,955,161(它在 64 位机器上可以做的最大数字)。