Facebook Interview Question
Developer Program EngineersCountry: India
public class PrimeFactors {
public PrimeFactors(int n) {
this.run(n);
}
private void run(int n) {
int m = 2 * n + 1;
for (int i = 2; i <= m; i++) {
if (this.isPrime(i))
System.out.println(i);
else
System.out.println(this.primeFactors(i));
}
}
private List<Integer> primeFactors(int numbers) {
int n = numbers;
List<Integer> factors = new ArrayList<Integer>();
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) {
factors.add(n);
}
return factors;
}
private boolean isPrime(int n) {
for (int i = 2; i <= (int) Math.sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
public static void main(String[] args) {
new PrimeFactors(10);
}
}
He might be asking you to pick up the prime numbers from 1...2n+1 numbers.
Which are not prime, just print out factors.
Sieve's method might work well here.
// Let's print only the factors >1
void print(int n) {
vector<int>numbers [2*n+1];
int M = 1 + 2 * n;
for (int j=2;j<=M;j++) {
if (numbers[j].size() == 0) // it's prime and print it.
else // Traverse the list and print all the factors
for (int k=j+j;k<=M;k+=j) {
numbers[k].push_back(j);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int num = 10734;
PrimeCalc pc = new PrimeCalc();
boolean res = pc.primeCalcMethod(num);
System.out.println(res);
// Factorize
if(!res){
FactorCalc fc = new FactorCalc();
fc.factorCalcMethod(num);
}
else
{
System.out.println(num);
}
}
public Boolean primeCalcMethod(int num){
if(num%2 == 0){
return false;
}
else
{
for(int i=3;i<13;i++){
if(num % i == 0 && num != i){
return false;
}
}
}
return true;
}
public void factorCalcMethod(int num){
while(num != 1){
if(num % 2 == 0){
System.out.println(2);
num = num / 2;
}
else{
for(int i=3;i<=num;i=i+2){
if(num % i == 0){
System.out.println(i);
num = num / i;
break;
}
}
}
}
}
This will do it in O(n^2) using a hashtable using so called Sieve algorithm
#include <iostream>
#include <iomanip>
using namespace std;
#define N 100000
class factors {
public:
int value;
factors * next;
};
void insert(factors **head,int value) {
factors * myFactor = new factors();
myFactor -> value = value;
myFactor -> next = *head;
* head = myFactor;
};
void printFactors(factors **head, int i){
factors * f = *head;
cout << i << ": " << setw(2);
if(f==0) cout << " prime";
while(f) {
cout << f->value;
if(f->next) cout << ",";
f=f->next;
}
cout << endl;
};
main()
{
factors **f = new factors * [2*N+1];
for(int i=2; i < 2*N+1 ; i++) {
for(int mul=2; (mul*i) < 2*N+1 ; mul++) {
insert(&(f[i*mul]),i);
}
}
for(int i=1; i < 2*N+1; i++) {
printFactors(&f[i],i);
}
}
public static void main(String[] a){
for(int i=1; i <= 2*(Integer.parseInt(a[0]))+1; i++){
primeFactor(i);
}
}
static void primeFactor(int n){
if(n==1){
System.out.println("Number 1 is prime");
return;
}
List<Integer> factors = new ArrayList<Integer>();
for(int i = 2; i<= n/2; i++){
if(n%i == 0){
factors.add(i);
}
}
if(factors.isEmpty()){
System.out.println("\nNumber "+n+" is prime");
return;
}
factors.add(1);
factors.add(n);
System.out.print(n+" is not prime factors are:");
for(int factor : factors){
System.out.print(factor+",");
}
}
I suppose I found a method work with better time approach(I think this comes from Eratosthenes sieve):
void find_prime_and_print_factors(std::std::vector<int> _return,int n)
{
int range = 2*n+1;
std::std::vector<int> num[range];
for(int i=1;i<range;i++)
{
int calnum = i+1;
if(num[i].isEmpty())
{
for(int j=2;j*calnum<=range;j++)
num[j*calnum-1].push_back(calnum);
_return.push_back(calnum);
}else{
std::cout<<calnum<<": ";
std::std::vector<int>::iterator itr;
for(itr=num[i].begin();itr!=num[i].end();++itr)
std::cout<<*itr<<" ";
std::cout<<std::endl;
}
}
}
void two_n_1_primes(unsigned n)
{
unsigned m = (n << 1) + 1;
for (unsigned p = 2; p <= m; ++p) {
unsigned x = p;
printf ("%d =", p);
for (unsigned j = 2; j * j <= x; ++j) {
while (x % j == 0) {
printf (" %d ", j);
x /= j;
}
}
if (x == p) {
printf(" is prime");
} else if (x != 1){
printf (" %d", x);
}
printf("\n");
}
}
This is not the best one but a normal approach
PrimeFactor(n)
{
int flag=0,i;
for(i=2;i<sqrt(n);i++)
{
if((n%i)==0)
{
print i
flag=1
}
}
if(flag==0) print n
}
void main()
{
for(int i=1;i<2*n+1;i++)
PrimeFactor(i);
}
That's a pretty ambiguous question. Could you please elaborate more? What is it meant by any of them not prime? I think you can find 2n+1 prime numbers for any value of n>0.
- Anonymous April 21, 2012