Super-Poulet numbers: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) (Added Perl) |
(Added C++ solution) |
||
Line 16: | Line 16: | ||
;*[[wp:Super-Poulet_number|Wikipedia: super-Poulet number]] |
;*[[wp:Super-Poulet_number|Wikipedia: super-Poulet number]] |
||
;*[[oeis:A050217|OEIS:A050217 - super-Poulet numbers]] |
;*[[oeis:A050217|OEIS:A050217 - super-Poulet numbers]] |
||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp">#include <algorithm> |
|||
#include <iostream> |
|||
#include <vector> |
|||
std::vector<unsigned int> divisors(unsigned int n) { |
|||
std::vector<unsigned int> result{1}; |
|||
unsigned int power = 2; |
|||
for (; (n & 1) == 0; power <<= 1, n >>= 1) |
|||
result.push_back(power); |
|||
for (unsigned int p = 3; p * p <= n; p += 2) { |
|||
size_t size = result.size(); |
|||
for (power = p; n % p == 0; power *= p, n /= p) |
|||
for (size_t i = 0; i != size; ++i) |
|||
result.push_back(power * result[i]); |
|||
} |
|||
if (n > 1) { |
|||
size_t size = result.size(); |
|||
for (size_t i = 0; i != size; ++i) |
|||
result.push_back(n * result[i]); |
|||
} |
|||
return result; |
|||
} |
|||
unsigned long long modpow(unsigned long long base, unsigned int exp, |
|||
unsigned int mod) { |
|||
if (mod == 1) |
|||
return 0; |
|||
unsigned long long result = 1; |
|||
base %= mod; |
|||
for (; exp != 0; exp >>= 1) { |
|||
if ((exp & 1) == 1) |
|||
result = (result * base) % mod; |
|||
base = (base * base) % mod; |
|||
} |
|||
return result; |
|||
} |
|||
bool is_prime(unsigned int n) { |
|||
if (n < 2) |
|||
return false; |
|||
if (n % 2 == 0) |
|||
return n == 2; |
|||
if (n % 3 == 0) |
|||
return n == 3; |
|||
if (n % 5 == 0) |
|||
return n == 5; |
|||
static constexpr unsigned int wheel[] = {4, 2, 4, 2, 4, 6, 2, 6}; |
|||
for (unsigned int p = 7;;) { |
|||
for (unsigned int w : wheel) { |
|||
if (p * p > n) |
|||
return true; |
|||
if (n % p == 0) |
|||
return false; |
|||
p += w; |
|||
} |
|||
} |
|||
} |
|||
bool is_poulet_number(unsigned int n) { |
|||
return modpow(2, n - 1, n) == 1 && !is_prime(n); |
|||
} |
|||
bool is_sp_num(unsigned int n) { |
|||
if (!is_poulet_number(n)) |
|||
return false; |
|||
auto div = divisors(n); |
|||
return all_of(div.begin() + 1, div.end(), |
|||
[](unsigned int d) { return modpow(2, d, d) == 2; }); |
|||
} |
|||
int main() { |
|||
std::cout.imbue(std::locale("")); |
|||
unsigned int n = 1, count = 0; |
|||
std::cout << "First 20 super-Poulet numbers:\n"; |
|||
for (; count < 20; n += 2) { |
|||
if (is_sp_num(n)) { |
|||
++count; |
|||
std::cout << n << ' '; |
|||
} |
|||
} |
|||
std::cout << '\n'; |
|||
for (unsigned int limit = 1000000; limit <= 10000000; limit *= 10) { |
|||
for (;;) { |
|||
n += 2; |
|||
if (is_sp_num(n)) { |
|||
++count; |
|||
if (n > limit) |
|||
break; |
|||
} |
|||
} |
|||
std::cout << "\nIndex and value of first super-Poulet greater than " |
|||
<< limit << ":\n#" << count << " is " << n << '\n'; |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 20 super-Poulet numbers: |
|||
341 1,387 2,047 2,701 3,277 4,033 4,369 4,681 5,461 7,957 8,321 10,261 13,747 14,491 15,709 18,721 19,951 23,377 31,417 31,609 |
|||
Index and value of first super-Poulet greater than 1,000,000: |
|||
#109 is 1,016,801 |
|||
Index and value of first super-Poulet greater than 10,000,000: |
|||
#317 is 10,031,653 |
|||
</pre> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |