Pseudo Primes Complete Solution

This article is part of the Scaler Topics Fortnightly Contest - 18

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Solution Approach

• The naive approach will be to iterate over all the numbers.
• Find their prime factors sum them and check if the sum is prime.
• But this is too slow as iterating over the range is O(N) and then prime factorisation is O(sqrt(N)) and then checking
• if the sum is prime is another O(sqrt(N)).
• Overall time complexity is O(N sqrt(N)) which is slow for the given constraints.
• Try to use Sieve of Eratosthenis.
• We use Sieve. Since we only need to sum the distinct prime factors whenever we find a prime number i using sieve
• we iterate over its multiples and add i to its sum. Keep another prefix array for pseudo primes update it while running sieve.

Time Complexity - O(N log log(N)) Space Complexity - O(N)

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation