Rosetta Code

Square-free integers: Difference between revisions

Page Discussion

Square-free integers (view source)

Revision as of 09:47, 6 February 2021

1,487 bytes removed ,  3 years ago
C++ - simpler and faster without using prime sieve
m (→‎{{header|Raku}}: remove un-needed '*.')
(C++ - simpler and faster without using prime sieve)
Line 349:
#include <iostream>
#include <string>
#include "prime_sieve.hpp"
 
using integer = uint64_t;
 
bool square_free(const prime_sieve& sieve, integer n) {
if (n % 4 == 0)
return false;
for (integer p = 3; p * p <= n; p += 2) {
ifinteger (sieve.is_prime(p)count && n % (p * p) == 0);
for (; n % returnp false== 0; n /= p) {
if (is_prime_[p/2++count -> 1]) {▼
return false;▼
}▼
}
return true;
}
 
void print_square_free_numbers(const prime_sieve& sieve, integer from, integer to) {
std::cout << "Square-free numbers between " << from
<< " and " << to << ":\n";
std::string line;
for (integer i = from; i <= to; ++i) {
if (square_free(sieve, i)) {
if (!line.empty())
line += ' ';
Line 382 ⟶ 384:
}
 
void print_square_free_count(const prime_sieve& sieve, integer from, integer to) {
integer count = 0;
for (integer i = from; i <= to; ++i) {
if (square_free(sieve, i))
++count;
}
Line 393 ⟶ 395:
 
int main() {
print_square_free_numbers(sieve1, 1000000000000LL, 1000000000145LL145);▼
prime_sieve sieve(1000001);
print_square_free_numbers(sieve1000000000000LL, 1, 1451000000000145LL);
print_square_free_count(sieve, 1, 1000000100);▼
▲ print_square_free_numbers(sieve, 1000000000000LL, 1000000000145LL);
print_square_free_count(sieve, 1, 1001000);
print_square_free_count(sieve, 1, 100010000);
print_square_free_count(sieve, 1, 10000100000);
print_square_free_count(sieve, 1, 1000001000000);
▲ print_square_free_count(sieve, 1, 1000000);
return 0;
}</lang>
 
Contents of prime_sieve.hpp:
<lang cpp>#ifndef PRIME_SIEVE_HPP
#define PRIME_SIEVE_HPP
 
#include <algorithm>
#include <vector>
 
/**
* A simple implementation of the Sieve of Eratosthenes.
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
*/
class prime_sieve {
public:
explicit prime_sieve(size_t);
bool is_prime(size_t) const;
private:
std::vector<bool> is_prime_;
};
 
/**
* Constructs a sieve with the given limit.
*
* @param limit the maximum integer that can be tested for primality
*/
inline prime_sieve::prime_sieve(size_t limit) {
limit = std::max(size_t(3), limit);
is_prime_.resize(limit/2, true);
for (size_t p = 3; p * p <= limit; p += 2) {
▲ if (is_prime_[p/2 - 1]) {
size_t inc = 2 * p;
for (size_t q = p * p; q <= limit; q += inc)
is_prime_[q/2 - 1] = false;
▲ }
}
}
 
/**
* Returns true if the given integer is a prime number. The integer
* must be less than or equal to the limit passed to the constructor.
*
* @param n an integer less than or equal to the limit passed to the
* constructor
* @return true if the integer is prime
*/
inline bool prime_sieve::is_prime(size_t n) const {
if (n == 2)
return true;
if (n < 2 || n % 2 == 0)
▲ return false;
return is_prime_.at(n/2 - 1);
}
 
#endif</lang>
 
{{out}}
Simonjsaunders
1,777

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/282981"