How to resolve the algorithm Totient function step by step in the FreeBASIC programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Totient function step by step in the FreeBASIC programming language

Table of Contents

Problem Statement

The   totient   function is also known as:

The totient function:

If the totient number   (for N)   is one less than   N,   then   N   is prime.

Create a   totient   function and: Show all output here.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Totient function step by step in the FreeBASIC programming language

Source code in the freebasic programming language

#define esPar(n) (((n) And 1) = 0)
#define esImpar(n)  (esPar(n) = 0)

Function Totient(n As Integer) As Integer
    'delta son números no divisibles por 2,3,5
    Dim delta(7) As Integer = {6,4,2,4,2,4,6,2}
    Dim As Integer i, quot, idx, result
    ' div mod por constante es rápido.
    'i = 2
    result = n
    If (2*2 <= n) Then
        If Not(esImpar(n)) Then
            ' eliminar números con factor 2,4,8,16,...
            While Not(esImpar(n))
                n = n \ 2
            Wend
            'eliminar los múltiplos de 2
            result -= result \ 2
        End If
    End If
    'i = 3
    If (3*3 <= n) And (n Mod 3 = 0) Then
        Do
            quot = n \ 3
            If n <> quot*3 Then
                Exit Do
            Else
                n = quot
            End If
        Loop Until false
        result -= result \ 3
    End If
    'i = 5
    If (5*5 <= n) And (n Mod 5 = 0) Then
        Do
            quot = n \ 5
            If n <> quot*5 Then
                Exit Do
            Else
                n = quot
            End If
        Loop Until false
        result -= result \ 5
    End If
    i = 7
    idx = 1
    'i = 7,11,13,17,19,23,29,...,49 ..
    While i*i <= n
        quot = n \ i
        If n = quot*i Then
            Do
                If n <> quot*i Then
                    Exit Do
                Else
                    n = quot
                End If
                quot = n \ i
            Loop Until false
            result -= result \ i
        End If
        i = i + delta(idx)
        idx = (idx+1) And 7
    Wend
    If n > 1 Then result -= result \ n
    Totient = result
End Function

Sub ContandoPrimos(n As Integer)
    Dim As Integer i, cnt = 0
    For i = 1 To n
        If Totient(i) = (i-1) Then cnt += 1
    Next i
    Print Using " #######      ######"; i-1; cnt
End Sub

Function esPrimo(n As Ulongint) As String
    esPrimo = "False"
    If n = 1 then Return "False"
    If (n=2) Or (n=3) Then Return "True"
    If n Mod 2=0 Then Exit Function
    If n Mod 3=0 Then Exit Function
    Dim As Ulongint limite = Sqr(N)+1
    For i As Ulongint = 6 To limite Step 6
        If N Mod (i-1)=0 Then Exit Function
        If N Mod (i+1)=0 Then Exit Function
    Next i
    Return "True"
End Function 

Sub display(n As Integer)
    Dim As Integer idx, phi
    If n = 0 Then Exit Sub
    Print "  n  phi(n)   esPrimo" 
    For idx = 1 To n
        phi = Totient(idx)
        Print Using "###   ###      \   \"; idx; phi; esPrimo(idx)
    Next idx
End Sub

Dim l As Integer
display(25)

Print Chr(10) & "   Limite  Son primos"
ContandoPrimos(25)
l = 100
Do
    ContandoPrimos(l)
    l = l*10
Loop Until l > 1000000
End

  

You may also check:How to resolve the algorithm Ascending primes step by step in the Delphi programming language
You may also check:How to resolve the algorithm Spiral matrix step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Convert seconds to compound duration step by step in the OCaml programming language
You may also check:How to resolve the algorithm Primality by trial division step by step in the HicEst programming language
You may also check:How to resolve the algorithm Time a function step by step in the Lasso programming language