Преобразование программы PARI в переполнение стека
Я нашел последовательность интересов в OEIS, и я хочу создать ту же последовательность в 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 в качестве пределов, потому что в противном случае значение результата переполняется типом длинной переменной.
Решение
У вас есть три программы, каждая из которых предназначена для разных целей.
Первый проверяет, является ли число 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;
}
Конечно, это не построчное преобразование; например, я не использовал логарифмы, так как точные логарифмы не встроены в C ++, как PARI. Это довольно быстро, он находит все 5-гладкие числа до 1 844 674 407 370 955 161 (самое большое, что он может сделать на 64-битной машине) за долю секунды.
Другие решения
Других решений пока нет …