Keep Only the Prime Numbers
Solve this ProblemEasy15 min
Topics
BasicsFunctionsMath
Companies
TCSInfosysWipro
Given an array
nums, return a new array containing only the values that are prime, in their original order.
Checking a single number for primality is its own exercise; here the point is decompositionDecompositionSplitting a problem into smaller named pieces — e.g. "is this prime?" and "keep the ones that pass".. Pulling the primality test out into isPrime(n) leaves the main function with one simple job, and gives the test a place where it is easy to improve: the helper stops at √n, while the inline version checks every candidate up to n − 1.
Test Case 1:
Input:nums = [10, 2, 9, 13, 1]
Output:[2, 13]
Explanation:2 and 13 have no divisors other than 1 and themselves; 10 and 9 do, and 1 is not prime.
Test Case 2:
Input:nums = [4, 6, 8]
Output:[]
Explanation:No primes at all, so the result is empty.
Constraints
- ◆
1 ≤ nums.length ≤ 30 - ◆
0 ≤ nums[i] ≤ 10000
Try the Dry Run
Approach & Solutions
Inline Trial Division up to n − 1Brute
For every value, assume it is prime if it is at least 2, then try every possible divisor from 2 up to value − 1 inside the loop. One divisor that divides evenly proves it is not prime. Keep the values that survive. The primality logic sits tangled inside the outer loop.
Time
O(n · m)Space
O(n)Java
class Solution {
public int[] primesIn(int[] nums) {
List<Integer> primes = new ArrayList<>();
for (int value : nums) {
boolean prime = value >= 2;
for (int d = 2; d < value; d++) {
if (value % d == 0) {
prime = false;
break;
}
}
if (prime) {
primes.add(value);
}
}
int[] result = new int[primes.size()];
for (int i = 0; i < result.length; i++) {
result[i] = primes.get(i);
}
return result;
}
}isPrime() Helper up to √nOptimal
Move the test into isPrime(n). It returns false for n < 2, and only tries divisors d while d × d ≤ n: if n had a divisor larger than √n, its partner divisor would be smaller than √n and would already have been found. The outer function simply keeps the values for which isPrime returns true.
Time
O(n · √m)Space
O(n)Java
class Solution {
boolean isPrime(int n) {
if (n < 2) {
return false;
}
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) {
return false;
}
}
return true;
}
public int[] primesIn(int[] nums) {
List<Integer> primes = new ArrayList<>();
for (int value : nums) {
if (isPrime(value)) {
primes.add(value);
}
}
return primes.stream().mapToInt(Integer::intValue).toArray();
}
}