文章/答案/技术大牛

发布

社区首页 >问答首页 >将PARI程序转换为C++

问将PARI程序转换为C++
EN

Stack Overflow用户

提问于 2016-08-08 20:41:58

回答 1查看 355关注 0票数 0

我在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++中生成序列。但我想我错过了某些数字，因为我没有通过在线集成开发环境中的一些测试。

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变量类型。

c++

pari

oeis

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-12-17 12:30:58

这里有三个程序，每个程序都有不同的用途。

第一个检查数字是否为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++中。它的速度非常快，它可以在不到一秒的时间内找到1,844,674,407,370,955,161 (它在64位机器上可以做到的最高值)的所有5-平滑数。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/38829540

复制

相似问题

问将PARI程序转换为C++
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问将PARI程序转换为C++EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问将PARI程序转换为C++
EN