90 lines
1.8 KiB
Text
90 lines
1.8 KiB
Text
NSInteger local fn GCD( n as NSInteger, d as NSInteger )
|
|
if ( d == 0 ) then return n else return fn GCD( d, n % d )
|
|
end fn = 0
|
|
|
|
NSInteger local fn Totient( n as NSInteger )
|
|
NSInteger tot = 0
|
|
for NSInteger m = 1 to n
|
|
if fn GCD( m, n ) = 1 then tot++
|
|
next
|
|
return tot
|
|
end fn = 0
|
|
|
|
BOOL local fn IsPowerful( m as NSInteger )
|
|
int n = m
|
|
int f = 2
|
|
double l = sqr(m)
|
|
|
|
if m <= 1 then return NO
|
|
while ( YES )
|
|
NSInteger q = n / f
|
|
if ( n % f ) == 0
|
|
if ( m % (f * f) ) then return NO
|
|
n = q
|
|
if f > n then exit while
|
|
else
|
|
f++
|
|
if ( f > l )
|
|
if ( m % (n * n) ) then return NO
|
|
exit while
|
|
end if
|
|
end if
|
|
wend
|
|
end fn = YES
|
|
|
|
BOOL local fn IsAchilles( n as NSInteger )
|
|
if fn IsPowerful(n) == NO then return NO
|
|
NSInteger m = 2
|
|
NSInteger a = m * m
|
|
do
|
|
do
|
|
if a == n then return NO
|
|
a *= m
|
|
until ( a > n )
|
|
m++
|
|
a = m * m
|
|
until ( a > n )
|
|
end fn = YES
|
|
|
|
local fn AchillesNumbers
|
|
print "First 50 Achilles numbers:"
|
|
NSInteger num = 0
|
|
NSInteger n = 1
|
|
|
|
CFTimeInterval t : t = fn CACurrentMediaTime
|
|
do
|
|
if fn IsAchilles( n )
|
|
printf @"%4d \b", n
|
|
num++
|
|
if ( num % 10 ) != 0 then printf @" \b" else print
|
|
end if
|
|
n++
|
|
until ( num >= 50 )
|
|
|
|
printf @"\n\nFirst 20 strong Achilles numbers:"
|
|
num = 0
|
|
n = 1
|
|
do
|
|
if fn IsAchilles(n) && fn IsAchilles( fn Totient(n) )
|
|
printf @"%5d \b", n
|
|
num++
|
|
if ( num % 5 ) != 0 then printf @" \b" else print
|
|
end if
|
|
n++
|
|
until ( num >= 20 )
|
|
|
|
printf @"\n"
|
|
for NSInteger i = 2 to 6
|
|
NSInteger inicio = fix( 10.0 ^ (i-1) )
|
|
num = 0
|
|
for n = inicio to inicio * 10 -1
|
|
if fn IsAchilles(n) then num++
|
|
next
|
|
printf @"Achilles numbers with %d digits: %d", i, num
|
|
next
|
|
printf @"\nCompute time: %.3f ms", (fn CACurrentMediaTime - t ) * 1000
|
|
end fn
|
|
|
|
fn AchillesNumbers
|
|
|
|
HandleEvents
|