Square-free integers: Difference between revisions

Content added Content deleted
m (Minor edit to C++ code)
m (C++ - renamed class)
Line 349: Line 349:
#include <iostream>
#include <iostream>
#include <string>
#include <string>
#include "sieve_of_eratosthenes.h"
#include "prime_sieve.hpp"


using integer = uint64_t;
using integer = uint64_t;


bool square_free(const sieve_of_eratosthenes& sieve, integer n) {
bool square_free(const prime_sieve& sieve, integer n) {
if (n % 4 == 0)
if (n % 4 == 0)
return false;
return false;
Line 363: Line 363:
}
}


void print_square_free_numbers(const sieve_of_eratosthenes& sieve, integer from, integer to) {
void print_square_free_numbers(const prime_sieve& sieve, integer from, integer to) {
std::cout << "Square-free numbers between " << from
std::cout << "Square-free numbers between " << from
<< " and " << to << ":\n";
<< " and " << to << ":\n";
Line 382: Line 382:
}
}


void print_square_free_count(const sieve_of_eratosthenes& sieve, integer from, integer to) {
void print_square_free_count(const prime_sieve& sieve, integer from, integer to) {
integer count = 0;
integer count = 0;
for (integer i = from; i <= to; ++i) {
for (integer i = from; i <= to; ++i) {
Line 393: Line 393:


int main() {
int main() {
sieve_of_eratosthenes sieve(1000001);
prime_sieve sieve(1000001);
print_square_free_numbers(sieve, 1, 145);
print_square_free_numbers(sieve, 1, 145);
print_square_free_numbers(sieve, 1000000000000LL, 1000000000145LL);
print_square_free_numbers(sieve, 1000000000000LL, 1000000000145LL);
Line 404: Line 404:
}</lang>
}</lang>


Contents of sieve_of_eratosthenes.h:
Contents of prime_sieve.hpp:
<lang cpp>#ifndef SIEVE_OF_ERATOSTHENES_H
<lang cpp>#ifndef PRIME_SIEVE_HPP
#define SIEVE_OF_ERATOSTHENES_H
#define PRIME_SIEVE_HPP


#include <algorithm>
#include <algorithm>
Line 415: Line 415:
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
*/
*/
class sieve_of_eratosthenes {
class prime_sieve {
public:
public:
explicit sieve_of_eratosthenes(size_t);
explicit prime_sieve(size_t);
bool is_prime(size_t) const;
bool is_prime(size_t) const;
private:
private:
Line 428: Line 428:
* @param limit the maximum integer that can be tested for primality
* @param limit the maximum integer that can be tested for primality
*/
*/
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t limit) {
inline prime_sieve::prime_sieve(size_t limit) {
limit = std::max(size_t(3), limit);
limit = std::max(size_t(3), limit);
is_prime_.resize(limit/2, true);
is_prime_.resize(limit/2, true);
Line 448: Line 448:
* @return true if the integer is prime
* @return true if the integer is prime
*/
*/
inline bool sieve_of_eratosthenes::is_prime(size_t n) const {
inline bool prime_sieve::is_prime(size_t n) const {
if (n == 2)
if (n == 2)
return true;
return true;
Retrieved from "https://rosettacode.org/wiki/Square-free_integers"