1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#!/usr/bin/env perl
use strict;
use warnings;
use feature qw'say state signatures';
no warnings qw'experimental::signatures';
# TASK #2 › Square-free Integer
# Submitted by: Mohammad S Anwar
#
# Write a script to generate all square-free integers <= 500.
#
# In mathematics, a square-free integer (or squarefree integer) is an
# integer which is divisible by no perfect square other than 1. That is, its
# prime factorization has exactly one factor for each prime that appears in
# it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not,
# because 18 is divisible by 9 = 3**2.
#
# Example
#
# The smallest positive square-free integers are
# 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, ...
run() unless caller();
sub run() {
# For this challenge we can take advantage of perls builtin `grep` routine
# to filter the list of integers <=500 with a is_squarefree routine that we
# are about to define.
my @square_free = grep { is_squarefree($_) } 1 .. 500;
# Afterwards we print the filtered list, seperated by commas.
say join( ', ', @square_free );
# Done.
}
sub is_squarefree($x) {
# According to the description, we have to do two things to check if a
# number is squarefree. First we get the prime factors of that number,
my @prime_factors = prime_factors($x);
# and then we check wether this list is free of duplicates.
return no_dupes(@prime_factors);
}
sub prime_factors($x) {
my @factors;
my $prime = 0;
while ( $x > 1 ) {
my $test_factor = primes($prime);
$prime++;
next unless $x % $test_factor == 0;
push @factors, $test_factor;
$x = $x / $test_factor;
$prime = 0;
}
return @factors;
}
sub primes($n) {
state @primes = (2);
for ( my $i = $primes[-1] + 1 ; $#primes < $n ; $i++ ) {
push @primes, $i if is_prime($i);
}
return $primes[$n];
}
sub is_prime($x) {
return 0 if $x <= 1;
return 1 if $x <= 3;
for ( my $i = 2 ; $i < sqrt($x) ; $i++ ) {
return 0 if $x % $i == 0;
}
return 1;
}
sub no_dupes(@xs) {
my %seen;
for my $x (@xs) {
return 0 if $seen{$x}++;
}
return 1;
}
|
