Bloomberg LP Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
C++11 sieve of eratosthenes
auto print_primes2 = [](int n) {
if (n >= 2) {
vector<bool> non_primes(n);
auto mark_non_primes = [&](int p) {
int non_prime = 0;
for (int i = 2; (non_prime = i * p) <= n; ++i) {
non_primes[non_prime-1] = true;
}
};
for (int i = 1; i < n; ++i) {
if (!non_primes[i]) {
cout << i+1 << " ";
mark_non_primes(i+1);
}
}
cout << endl;
}
};
If I understood the algorithm correctly here is the solution in Ruby
def findPrimes (nums)
nums.sort!
h = Hash[nums.map{ |x| [x, false] }]
primes = [ ]
curr = 0
set = false
num = 0
while (curr < nums.length)
num = nums[curr]
h.each do |key, value|
if(key%num == 0)
value = true
set = true
end
end
primes << num if !set
nums[curr, nums.length].each do |n|
if (h[n] == false)
curr = nums.index(n)
break
end
end
end
return primes
end
Jave implementation of sieve
public void print_pr_n(int n){
HashSet<Integer> composites = new HashSet<Integer>(n);
if(n >= 1) System.out.print("1, ");
for(int i = 2; i <= n; i++){
if(composites.contains(i)) continue;
System.out.print(i + ", ");
if(i <= Math.sqrt(n)+1){
for(int j = 2; i*j <= n; j++){
composites.add(i*j);
}
}
}
}
sieve of eratosthenes. For 1 to 100.
boolean primes[] = new boolean[100];
int i,j;
int cnt=0;
for(i=0;i<10;i++)
{
primes[i]=true;
}
for(i=2;i<Math.sqrt(10);i++)
{
if(primes[i]==true)
{
j=i*i;
while(j < 100)
{
primes[j]=false;
cnt++;
j=j+i;
}
}
}
System.out.println("Primes are");
for(i=2;i<10;i++)
{
if(primes[i]==true)
System.out.print(i + " ");
}
javaeediag has a pretty good solution, building up a HashSet to check against. This is definitely a problem which can be solved with dynamic programming. However, we can modify that algorithm to shave off a tiny bit of run time and take it from polynomial time to linear by building our set first, rather than inside of a loop.
public static void printPrimes(int num) {
HashSet<Integer> composites = new HashSet<Integer>(num);
if (num >= 1)
System.out.print("1");
if (num >= 2)
System.out.print(", 2");
if (num >= 3)
System.out.print(", 3, 5");
if(num > 4){
for (int i = 2; i < num; i++)
if ((i % 3) == 0 || (i % 5) == 0 || (i % 7) == 0)
composites.add(i);
for (int i = 7; i < num; i += 2)
if (!composites.contains(i))
System.out.print(", " + i);
}
}
Could you please help me with the following 2 questions:
1. For the condition num >= 3, we print 3 & 5. But what if num = 4?
2. Shouldn't the first for loop contain a condition for i%2 ?
Wouldn't a number like 8 fail that test and hence not get added into the composites HashSet?
I modified your program. Of course, it could do with some fine tuning. It appears to be producing the output correctly. Please share your thoughts. Thanks!
public static void printPrimes(int num)
{
HashSet<Integer>primes = new HashSet<Integer>(num);
//Add the numbers that will help us with the conditions.
primes.add(1);
primes.add(2);
primes.add(3);
primes.add(5);
primes.add(7);
if(num > 4){
for (int i = 2; i < num; i++)
{
if ((i % 2) ==0 || (i % 3) == 0 || (i % 5) == 0 || (i % 7) == 0)
continue;
else
primes.add(i);
}
for (int i = 1; i < num; i++)
{
if (primes.contains(i) && i<=num)
System.out.print("\n" + i);
}
}
}
public class Prime {
public static void main(String[] args) {
System.out.print("Enter a number : ");
int number,counter;
Scanner sc = new Scanner(System.in);
number = sc.nextInt();
System.out.print("Prime number before " + number + " are : ");
for(int i=1;i<number;i++){
counter=0;
for(int j=1;j<=i;j++){
if(i%j==0)
counter++;
}
if(counter<=2)
System.out.print(i + " ");
}
}
}
#include "MyHeader.h"
#include <vector>
std::vector<int> AllPrimeNumbersLessThan(int n)
{
std::vector<int> resultArray(n+1, 1);
for(int i=3; i<=n; i++)
{
if(resultArray[i]==1)
{
int mul_factor = 2;
while(mul_factor*i<=n)
{
resultArray[mul_factor*i] = 0;
mul_factor++;
}
}
}
return resultArray;
};
int main()
{
std::vector<int> vec = AllPrimeNumbersLessThan(50);
std::cout<<"All Prime Numbers less than 50 are: ";
for(int i=1; i<vec.size(); i++)
if(vec[i])
std::cout<<" "<<i;
return 0;
};
#include "MyHeader.h"
#include <vector>
std::vector<int> AllPrimeNumbersLessThan(int n)
{
std::vector<int> resultArray(n+1, 1);
for(int i=3; i<=n; i++)
{
if(resultArray[i]==1)
{
int mul_factor = 2;
while(mul_factor*i<=n)
{
resultArray[mul_factor*i] = 0;
mul_factor++;
}
}
}
return resultArray;
};
int main()
{
std::vector<int> vec = AllPrimeNumbersLessThan(50);
std::cout<<"All Prime Numbers less than 50 are: ";
for(int i=1; i<vec.size(); i++)
if(vec[i])
std::cout<<" "<<i;
return 0;
};
///#include "MyHeader.h"
#include <vector>
std::vector<int> AllPrimeNumbersLessThan(int n)
{
std::vector<int> resultArray(n+1, 1);
for(int i=3; i<=n; i++)
{
if(resultArray[i]==1)
{
int mul_factor = 2;
while(mul_factor*i<=n)
{
resultArray[mul_factor*i] = 0;
mul_factor++;
}
}
}
return resultArray;
};
int main()
{
std::vector<int> vec = AllPrimeNumbersLessThan(50);
std::cout<<"All Prime Numbers less than 50 are: ";
for(int i=1; i<vec.size(); i++)
if(vec[i])
std::cout<<" "<<i;
return 0;
};\\\
#include "MyHeader.h"
#include <vector>
std::vector<int> AllPrimeNumbersLessThan(int n)
{
std::vector<int> resultArray(n+1, 1);
for(int i=3; i<=n; i++)
{
if(resultArray[i]==1)
{
int mul_factor = 2;
while(mul_factor*i<=n)
{
resultArray[mul_factor*i] = 0;
mul_factor++;
}
}
}
return resultArray;
};
int main()
{
std::vector<int> vec = AllPrimeNumbersLessThan(50);
std::cout<<"All Prime Numbers less than 50 are: ";
for(int i=1; i<vec.size(); i++)
if(vec[i])
std::cout<<" "<<i;
return 0;
};
Sieve Implementation in Java:
int[] primes = new int[num-1];
for (int i = 0; i < primes.length; ++i) {
primes[i] = i+2;
}
for ( int i = 0 ; i < primes.length && primes[i] != -1 ; ++i ) {
int jmp = primes[i];
int index = i;
while( (index+jmp) < primes.length ) {
index = index+jmp;
primes[index] = -1;
}
}
public class PrimesTillN {
public static void main(String[] args){
PrimesTillN ptn=new PrimesTillN();
int input=30;
for(int i=2; i<input; i++){
if(ptn.IsPrime(i)){
System.out.println(i);
}
}
}
public boolean IsPrime(int n){
double sqrt=Math.sqrt(n);
for(int i=2; i<=sqrt; i++)
{
if (n%i==0){
return false;
}
}
return true;
}
}
import java.util.ArrayList;
public class SmallerPrime {
public ArrayList<Integer> prime(int number) {
ArrayList<Integer> list = new ArrayList<Integer>();
int i;
int flag = 0;
for(i = (number - 1) ; i>1 ; i--) {
for(int j=2; j<i ; j++) {
if(i % j == 0){
flag = 1;
break;
}
}
if( flag == 0) {
list.add(i);
}
flag = 0;
}
System.out.println("The prime numbers are: "+list);
return list;
}
public static void main(String [] args) {
SmallerPrime obj = new SmallerPrime();
obj.prime(123);
}
}
sieve of eratosthenes
- mike tyson October 31, 2013