Frontend School

Sum of Coprime Integers

DSA
medium

Sum of Coprime Integers

Medium
Math
Number Theory
Inclusion-Exclusion

Overview

In the realm of database optimization, efficiently counting or summing records based on certain divisibility properties can significantly impact query performance. Imagine a scenario where you need to aggregate data points, but only for those entries whose unique identifiers are "relatively prime" to a specific system constant. This problem challenges you to calculate the sum of all positive integers up to a given limit that share no common prime factors with another specified integer, simulating a core operation in such optimized data retrieval systems.

What you need to do / Task

You are tasked with implementing a function sumOfCoprimeIntegers that takes two positive integers, N and P, and returns the sum of all positive integers x such that 1 <= x <= N and gcd(x, P) = 1.

Specifically, your function should:

  1. Identify the distinct prime factors of P.
  2. Utilize these prime factors to determine which integers up to N are coprime to P.
  3. Calculate the sum of all such integers.

Input & output

  • Input:
    • N: A positive integer representing the upper limit (inclusive).
    • P: A positive integer (greater than 1) whose prime factors determine coprimality.
  • Output:
    • A single integer representing the sum of all x (1 <= x <= N) such that gcd(x, P) = 1.

Clarifications

  • gcd(a, b) denotes the greatest common divisor of a and b.
  • Two integers a and b are coprime (or relatively prime) if gcd(a, b) = 1. This is equivalent to saying they share no common prime factors.
  • The result will fit within a standard 64-bit signed integer type, which in JavaScript is number (accurate up to 2^53 - 1).

Examples

1

Example 1

Input:

N = 10, P = 2

Output:

25

Note:

Numbers coprime to 2 up to 10 are 1, 3, 5, 7, 9. Their sum is 25.

2

Example 2

Input:

N = 10, P = 6

Output:

13

Note:

Numbers coprime to 6 up to 10 are 1, 5, 7. Their sum is 13.

3

Example 3

Input:

N = 20, P = 30

Output:

68

Note:

Numbers coprime to 30 up to 20 are 1, 7, 11, 13, 17, 19. Their sum is 68.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^8
  • 2 <= P <= 10^6
  • P will not be 1.

What interviewers evaluate

  • Correctness and Efficiency: The solution must correctly identify coprime numbers and sum them, with an efficient algorithm that scales well with N and P.
  • Algorithm Design: Demonstrate a clear understanding and application of number theory principles, specifically prime factorization and the principle of inclusion-exclusion.
  • Code Structure and Readability: Well-organized code with meaningful variable names and comments where necessary.
  • Edge Case Handling: Correct behavior for minimum N and P values, and when P is a prime number or a power of a prime.

Out of scope

  • Handling negative inputs for N or P.
  • Optimizations for extremely large N (beyond 10^8) that would require BigInt or custom large number arithmetic.

Loading editor...