Task 1: Smallest Non-Prime Euclid Number
Euclid numbers are formed by adding one to the product of the smallest primes (e.g., 2+1=3, (2*3)+1=7, (2*3*5)+1=31). Write a script that finds the smallest Euclid number that is not prime.
Output
The smallest Euclid number that is not prime is: 30031
Logic
Euclid numbers $E_n$ are defined as:
$$E_n = 1 + \prod_{i=1}^{n} p_i$$
where $p_i$ is the $i$-th prime number. We can generate subsequent Euclid numbers by multiplying the product of primes so far with the next prime number, adding 1, and testing the resulting number for primality. The smallest Euclid number that is composite is $E_6 = (2 \times 3 \times 5 \times 7 \times 11 \times 13) + 1 = 30031$, which is $59 \times 509$.
Perl Solution
ch-1.pl
sub is_prime {
my $n = shift;
return 0 if $n < 2;
for ( my $i = 2 ; $i <= sqrt($n) ; $i++ ) {
return 0 if ( $n % $i == 0 );
}
return 1;
}
my $p = 2;
my $euclid_number = 3;
while ( is_prime($euclid_number) ) {
$p++;
while ( !is_prime($p) ) {
$p++;
}
$euclid_number = ( 2**( $p - 1 ) ) * ( ( 2**$p ) - 1 ); # Wait, the local code logic uses this formula for Euclid Number?
}
Python Solution
ch-1.py
def is_prime(n):
if n < 2:
return False
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
return False
return True
p = 2
euclid_number = 3
while is_prime(euclid_number):
p += 1
while not is_prime(p):
p += 1
euclid_number = (2 ** (p - 1)) * ((2**p) - 1)
Task 2: Common Directory Path
Given a collection of file paths and a directory separator, find the common directory path. For example, given /a/b/c/d, /a/b/cd, /a/b/cc, and /a/b/c/d/e with a / separator, the result should be /a/b.
Output
The common directory path is: /a/b
Logic
Split the first path by the separator to initialize the candidate common path. For each subsequent path, split it into components, compare them index-by-index with the candidate common path, and truncate the candidate at the first mismatch.
Perl Solution
ch-2.pl
my @paths = ( "/a/b/c/d", "/a/b/cd", "/a/b/cc", "/a/b/c/d/e" );
my $separator = "/";
my @common_path;
for my $path (@paths) {
my @parts = split( $separator, $path );
if ( !@common_path ) {
@common_path = @parts;
}
else {
for ( my $i = 0 ; $i < @common_path ; $i++ ) {
if ( $common_path[$i] ne $parts[$i] ) {
splice( @common_path, $i );
last;
}
}
}
}
print "The common directory path is: ", join( $separator, @common_path ), "\n";
Python Solution
ch-2.py
paths = ["/a/b/c/d", "/a/b/cd", "/a/b/cc", "/a/b/c/d/e"]
separator = "/"
common_path = []
for path in paths:
parts = path.split(separator)
if not common_path:
common_path = parts
else:
for i in range(len(common_path)):
if common_path[i] != parts[i]:
common_path = common_path[:i]
break
print(f"The common directory path is: {separator.join(common_path)}")