Radical of an integer: Difference between revisions
Content added Content deleted
(→{{header|Free Pascal}}: added modified fast consecutive factors of integer. Yes, it's lengthy.) |
(Added XPL0 example.) |
||
Line 1,252: | Line 1,252: | ||
78,735 |
78,735 |
||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang "XPL0">include xpllib; \for Print and IsPrime |
|||
proc Radical(N); \Return radical of N |
|||
int N, D, D0, P; |
|||
[D:= 2; D0:= 0; P:= 1; |
|||
while N >= D*D do |
|||
[while rem(N/D) = 0 do |
|||
[if D # D0 then |
|||
[P:= P*D; |
|||
D0:= D; |
|||
]; |
|||
N:= N/D; |
|||
]; |
|||
D:= D+1; |
|||
]; |
|||
if D # D0 then P:= P*N; |
|||
return P; |
|||
]; |
|||
func DistinctFactors(N); \Return count of distinct factors of N |
|||
int N, D, D0, C; |
|||
[D:= 2; D0:= 0; C:= 0; |
|||
while N >= D*D do |
|||
[while rem(N/D) = 0 do |
|||
[if D # D0 then |
|||
[C:= C+1; |
|||
D0:= D; |
|||
]; |
|||
N:= N/D; |
|||
]; |
|||
D:= D+1; |
|||
]; |
|||
if D # D0 and N # 1 then C:= C+1; |
|||
return C; |
|||
]; |
|||
int N, C, A(10), PC, PPC, P2, P; |
|||
[Print("The radicals for the first 50 positive integers are:\n"); |
|||
for N:= 1 to 50 do |
|||
[Print("%4d", Radical(N)); |
|||
if rem(N/10) = 0 then CrLf(0); |
|||
]; |
|||
Print("\n"); |
|||
Print("Radical for %6,d: %6,d\n", 99_999, Radical( 99_999)); |
|||
Print("Radical for %6,d: %6,d\n", 499_999, Radical(499_999)); |
|||
Print("Radical for %6,d: %6,d\n", 999_999, Radical(999_999)); |
|||
for N:= 0 to 9 do A(N):= 0; |
|||
for N:= 1 to 1_000_000 do |
|||
[C:= DistinctFactors(N); |
|||
A(C):= A(C)+1; |
|||
]; |
|||
Print("\nBreakdown of numbers of distinct prime factors |
|||
for positive integers from 1 to 1,000,000:\n"); |
|||
C:= 0; |
|||
for N:= 0 to 9 do |
|||
[if A(N) > 0 then |
|||
Print(" %d: %6,d\n", N, A(N)); |
|||
C:= C + A(N); |
|||
]; |
|||
Print(" ---------\n %,d\n", C); |
|||
\Bonus (algorithm from Wren): |
|||
PC:= 0; |
|||
for N:= 1 to 1_000_000 do |
|||
if IsPrime(N) then PC:= PC+1; |
|||
Print("\nNumber of primes: %5,d\n", PC); |
|||
PPC:= 0; |
|||
for P:= 1 to sqrt(1_000_000) do |
|||
[if IsPrime(P) then |
|||
[P2:= P; |
|||
loop [P2:= P2 * P; |
|||
if P2 > 1_000_000 then quit; |
|||
PPC:= PPC+1; |
|||
]; |
|||
]; |
|||
]; |
|||
Print("Number of powers: %5,d\n", PPC); |
|||
if IsPrime(N) then PC:= PC+1; |
|||
Print("Total : %5,d\n", PC+PPC); |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The radicals for the first 50 positive integers are: |
|||
1 2 3 2 5 6 7 2 3 10 |
|||
11 6 13 14 15 2 17 6 19 10 |
|||
21 22 23 6 5 26 3 14 29 30 |
|||
31 2 33 34 35 6 37 38 39 10 |
|||
41 42 43 22 15 46 47 6 7 10 |
|||
Radical for 99,999: 33,333 |
|||
Radical for 499,999: 3,937 |
|||
Radical for 999,999: 111,111 |
|||
Breakdown of numbers of distinct prime factors |
|||
for positive integers from 1 to 1,000,000: |
|||
0: 1 |
|||
1: 78,734 |
|||
2: 288,726 |
|||
3: 379,720 |
|||
4: 208,034 |
|||
5: 42,492 |
|||
6: 2,285 |
|||
7: 8 |
|||
--------- |
|||
1,000,000 |
|||
Number of primes: 78,498 |
|||
Number of powers: 236 |
|||
Total : 78,734 |
|||
</pre> |
</pre> |