Proper divisors: Difference between revisions
Content added Content deleted
(→{{header|ALGOL 68}}: Use a less pessimised algorithm) |
(added GFA Basic example) |
||
Line 766: | Line 766: | ||
from 1 to 20000 |
from 1 to 20000 |
||
15120 has max proper divisors: 79 |
15120 has max proper divisors: 79 |
||
</pre> |
|||
=={{header|GFA Basic}}== |
|||
<lang> |
|||
OPENW 1 |
|||
CLEARW 1 |
|||
' |
|||
' Array f% is used to hold the divisors |
|||
DIM f%(SQR(20000)) ! cannot redim arrays, so set size to largest needed |
|||
' |
|||
' 1. Show proper divisors of 1 to 10, inclusive |
|||
' |
|||
FOR i%=1 TO 10 |
|||
num%=@proper_divisors(i%) |
|||
PRINT "Divisors for ";i%;":"; |
|||
FOR j%=1 TO num% |
|||
PRINT " ";f%(j%); |
|||
NEXT j% |
|||
PRINT |
|||
NEXT i% |
|||
' |
|||
' 2. Find (smallest) number <= 20000 with largest number of proper divisors |
|||
' |
|||
result%=1 ! largest so far |
|||
number%=0 ! its number of divisors |
|||
FOR i%=1 TO 20000 |
|||
num%=@proper_divisors(i%) |
|||
IF num%>number% |
|||
result%=i% |
|||
number%=num% |
|||
ENDIF |
|||
NEXT i% |
|||
PRINT "Largest number of divisors is ";number%;" for ";result% |
|||
' |
|||
~INP(2) |
|||
CLOSEW 1 |
|||
' |
|||
' find the proper divisors of n%, placing results in f% |
|||
' and return the number found |
|||
' |
|||
FUNCTION proper_divisors(n%) |
|||
LOCAL i%,root%,count% |
|||
' |
|||
ARRAYFILL f%(),0 |
|||
count%=1 ! index of next slot in f% to fill |
|||
' |
|||
IF n%>1 |
|||
f%(count%)=1 |
|||
count%=count%+1 |
|||
root%=SQR(n%) |
|||
FOR i%=2 TO root% |
|||
IF n% MOD i%=0 |
|||
f%(count%)=i% |
|||
count%=count%+1 |
|||
IF i%*i%<>n% ! root% is an integer, so check if i% is actual square root of n% |
|||
f%(count%)=n%/i% |
|||
count%=count%+1 |
|||
ENDIF |
|||
ENDIF |
|||
NEXT i% |
|||
ENDIF |
|||
' |
|||
RETURN count%-1 |
|||
ENDFUNC |
|||
</lang> |
|||
Output is: |
|||
<pre> |
|||
Divisors for 1: |
|||
Divisors for 2: 1 |
|||
Divisors for 3: 1 |
|||
Divisors for 4: 1 2 |
|||
Divisors for 5: 1 |
|||
Divisors for 6: 1 2 3 |
|||
Divisors for 7: 1 |
|||
Divisors for 8: 1 2 4 |
|||
Divisors for 9: 1 3 |
|||
Divisors for 10: 1 2 5 |
|||
Largest number of divisors is 79 for 15120 |
|||
</pre> |
</pre> |
||