Dado um inteiro N , a tarefa é encontrar a soma de todos os números no intervalo [1, N] que são primos com o número N fornecido .

Exemplos:

Entrada: N = 5
Saída: 10
Explicação: Os
números que são primos com 5 são {1, 2, 3, 4}.
Portanto, a soma é dada por 1 + 2 + 3 + 4 = 10.

Entrada: N = 6
Saída: 5
Explicação: Os
números que são primos de 6 são {1, 5}.
Portanto, a soma necessária é igual a 1 + 5 = 6

Abordagem: A ideia é iterar no intervalo [1, N] e, para cada número, verificar se seu GCD com N é igual a 1 ou não. Se for verdade, para qualquer número, inclua esse número na soma resultante. Siga as etapas abaixo para resolver o problema:

• Inicialize a soma como 0.
• Itere no intervalo [1, N] e se GCD de i e N for 1 , adicione i para somar .
• Após concluir as etapas acima, imprima o valor da soma obtida.

Abaixo está a implementação da abordagem acima:

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to return gcd of a and b
int gcd(int a, int b)
{
    // Base Case
    if (a == 0)
        return b;
 
    // Recursive GCD
    return gcd(b % a, a);
}
 
// Function to calculate the sum of all
// numbers till N that are coprime with N
int findSum(unsigned int N)
{
    // Stores the resultant sum
    unsigned int sum = 0;
 
    // Iterate over [1, N]
    for (int i = 1; i < N; i++) {
 
        // If gcd is 1
        if (gcd(i, N) == 1) {
 
            // Update sum
            sum += i;
        }
    }
 
    // Return the final sum
    return sum;
}
 
// Driver Code
int main()
{
    // Given N
    int N = 5;
 
    // Function Call
    cout << findSum(N);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to return gcd
// of a and b
static int gcd(int a,
               int b)
{
  // Base Case
  if (a == 0)
    return b;
 
  // Recursive GCD
  return gcd(b % a, a);
}
 
// Function to calculate the
// sum of all numbers till N
// that are coprime with N
static int findSum(int N)
{
  // Stores the resultant sum
  int sum = 0;
 
  // Iterate over [1, N]
  for (int i = 1; i < N; i++)
  {
    // If gcd is 1
    if (gcd(i, N) == 1)
    {
      // Update sum
      sum += i;
    }
  }
 
  // Return the final sum
  return sum;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given N
  int N = 5;
 
  // Function Call
  System.out.print(findSum(N));
}
}
 
// This code is contributed by gauravrajput1

# Python program for
# the above approach
 
# Function to return gcd
# of a and b
def gcd(a, b):
    # Base Case
    if (a == 0):
        return b;
 
    # Recursive GCD
    return gcd(b % a, a);
 
# Function to calculate the
# sum of all numbers till N
# that are coprime with N
def findSum(N):
    # Stores the resultant sum
    sum = 0;
 
    # Iterate over [1, N]
    for i in range(1, N):
        # If gcd is 1
        if (gcd(i, N) == 1):
            # Update sum
            sum += i;
 
    # Return the final sum
    return sum;
 
# Driver Code
if __name__ == '__main__':
    # Given N
    N = 5;
 
    # Function Call
    print(findSum(N));
 
# This code is contributed by Rajput-Ji

// C# program for the above approach
using System;
class GFG{
 
// Function to return gcd
// of a and b
static int gcd(int a,
               int b)
{
  // Base Case
  if (a == 0)
    return b;
 
  // Recursive GCD
  return gcd(b % a, a);
}
 
// Function to calculate the
// sum of all numbers till N
// that are coprime with N
static int findSum(int N)
{
  // Stores the resultant sum
  int sum = 0;
 
  // Iterate over [1, N]
  for (int i = 1; i < N; i++)
  {
    // If gcd is 1
    if (gcd(i, N) == 1)
    {
      // Update sum
      sum += i;
    }
  }
 
  // Return the readonly sum
  return sum;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given N
  int N = 5;
 
  // Function Call
  Console.Write(findSum(N));
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program for the above approach
 
// Function to return gcd of a and b
function gcd(a, b)
{
    // Base Case
    if (a == 0)
        return b;
 
    // Recursive GCD
    return gcd(b % a, a);
}
 
// Function to calculate the sum of all
// numbers till N that are coprime with N
function findSum(N)
{
    // Stores the resultant sum
    var sum = 0;
 
    // Iterate over [1, N]
    for (var i = 1; i < N; i++) {
 
        // If gcd is 1
        if (gcd(i, N) == 1) {
 
            // Update sum
            sum += i;
        }
    }
 
    // Return the final sum
    return sum;
}
 
// Driver Code
// Given N
var N = 5;
 
// Function Call
document.write(findSum(N));
 
 
</script>

10

Complexidade de tempo: O (N)
Espaço auxiliar: O (1)