Square-free integers: Difference between revisions
Content added Content deleted
(added Tcl) |
m (Reformatted to reduce line count) |
||
| Line 353: | Line 353: | ||
using integer = uint64_t; |
using integer = uint64_t; |
||
bool square_free(const sieve_of_eratosthenes& sieve, integer n) |
bool square_free(const sieve_of_eratosthenes& sieve, integer n) { |
||
{ |
|||
if (n % 4 == 0) |
if (n % 4 == 0) |
||
return false; |
return false; |
||
for (integer p = 3; p * p <= n; p += 2) |
for (integer p = 3; p * p <= n; p += 2) { |
||
{ |
|||
if (sieve.is_prime(p) && n % (p * p) == 0) |
if (sieve.is_prime(p) && n % (p * p) == 0) |
||
return false; |
return false; |
||
| Line 365: | Line 363: | ||
} |
} |
||
void print_square_free_numbers(const sieve_of_eratosthenes& sieve, integer from, integer to) |
void print_square_free_numbers(const sieve_of_eratosthenes& 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"; |
||
std::string line; |
std::string line; |
||
for (integer i = from; i <= to; ++i) |
for (integer i = from; i <= to; ++i) { |
||
| ⚫ | |||
{ |
|||
| ⚫ | |||
{ |
|||
if (!line.empty()) |
if (!line.empty()) |
||
line += ' '; |
line += ' '; |
||
line += std::to_string(i); |
line += std::to_string(i); |
||
if (line.size() >= 80) |
if (line.size() >= 80) { |
||
{ |
|||
std::cout << line << '\n'; |
std::cout << line << '\n'; |
||
line.clear(); |
line.clear(); |
||
| Line 388: | Line 382: | ||
} |
} |
||
void print_square_free_count(const sieve_of_eratosthenes& sieve, integer from, integer to) |
void print_square_free_count(const sieve_of_eratosthenes& 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) { |
||
{ |
|||
if (square_free(sieve, i)) |
if (square_free(sieve, i)) |
||
++count; |
++count; |
||
| Line 400: | Line 392: | ||
} |
} |
||
int main() |
int main() { |
||
{ |
|||
sieve_of_eratosthenes sieve(1000001); |
sieve_of_eratosthenes sieve(1000001); |
||
print_square_free_numbers(sieve, 1, 145); |
print_square_free_numbers(sieve, 1, 145); |
||