Epic Systems Interview Question Software Engineer / Developers
public void findPrime(int n)
{
for(int i = 2 ; i < n ; i ++)
{
flag = false ;
for(int j = 2 ; j < Math.sqrt(i * 1.0) ; j++)
{
if(i%j==0)
{
flag = true ;
break ;
}
}
if(flag ==false)
{
System.out.println(i +" is a Prime Number");
}
}
}
public void findPrime(int num)
{
for (int i=1; i<=num; i++)
{
if(isPrime(i))
System.out.println(i +" is a Prime Number");
}
}
public boolean isPrime(int num)
{
int divisor = Math.floor(Math.sqrt(num)); //Our largest divisor
if (num == 2)
return true;
else if (num < 2)
return false;
for (i = 2; i <= divisor; i++)
{
if (num % i == 0)
return false;
}
return true;
}
void printPrime(int N)
{
int * numbers = malloc( N * sizeof(int));
for(int i = 0; i < N; i++)
{
*(numbers + i) = i+1;
}
for(int i = 1; i < N; i++)
{
if(*(numbers + i) != 0)
{
for(int j = i+1; i < N; j++)
{
if(*(numbers + j) % *(numbers + i) == 0)
{
*(numbers + j) = 0;
}
}
}
}
for(int i = 1; i < N; i++)
{
printf("%d is a prime\n", *(numbers + i));
}
free(numbers);
}
<pre lang="" line="1" title="CodeMonkey38306" class="run-this">public void PrimeNumbers (int N) {
boolean not_prime = false;
for (int i=2; i<=N; i++) {
int j = 2;
not_prime = false;
while (j <= sqrt(i)) {
if (i%j == 0) {
not_prime = true;
break;
} // end if
j++;
} // end while
if (!not_prime) {
System.out.println("Prime number:" + i);
} // end if
} // end for
}
</pre><pre title="CodeMonkey38306" input="yes">
19</pre>
public class getprime {
public static void main(String[] args) {
for(int i=0; i<50; i++) {
if(isPrime(i)) {
System.out.println(i);
}
}
}
private static boolean isPrime(int n) {
boolean result = false;
if(n == 2 || n == 3) return true;
for (int i = 2; i <= (int) Math.sqrt(n); i++) {
if (n % i == 0) {
result = false;
break;
} else
result = true;
}
return result;
}
}
public class Prime {
public static void main(String args[]) {
int p = 329;
boolean check = false;
for (int i = 2; i <= p; i++) {
if (i == 2 || i == 3)
System.out.println(i);
for (int j = 2; j <= i / 2; j++) {
if (i % j == 0) {
check = false;
break;
} else
check = true;
}
if (check)
System.out.println(i);
}
}
}
Here is a working code in C++. I have applied Sieve of Eratosthenes:
#include <cstdio>
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int n, i, j, **arr, k, x, y;
cin>>n;
arr=new int *[(int)ceil(sqrt(n))];
for (i=0; i<(int)ceil(sqrt(n)); i++)
{
arr[i]=new int[(int)ceil(sqrt(n))];
}
for (i=0; i<(int)ceil(sqrt(n)); i++)
{
for (j=0; j<(int)ceil(sqrt(n)); j++)
{
arr[i][j]=(i*((int)ceil((sqrt(n)))))+(j+1);
}
}
for (i=0; i<(int)ceil(sqrt(n)); i++)
{
for (j=0; j<(int)ceil(sqrt(n)); j++)
{
if (arr[i][j]==-1 || arr[i][j]==1)
{
continue;
}
else
{
for (k=(2*arr[i][j]); k<=n; k++)
{
x=k/((int)ceil((sqrt(n))));
y=k%(((int)ceil((sqrt(n)))));
if(y==0)
{
x--;
y=((int)ceil((sqrt(n))));
}
y--;
if (k%arr[i][j]==0)
{
arr[x][y]=-1;
}
}
}
}
}
for (i=0; i<(int)ceil(sqrt(n)); i++)
{
for (j=0; j<(int)ceil(sqrt(n)); j++)
{
if (arr[i][j]==1)
{
continue;
}
if ( (arr[i][j]!=-1 && arr[i][j]<=n))
{
cout<<arr[i][j]<<" ";
}
}
}
cout<<endl;
return 0;
}
Python(Sieve of Eratosthenes)
def main():
N = 5000
a = [i for i in range(0,N+1)]
f=1
p=2
while f==1:
i=2
while i*p < N+1:
a[i*p] = 0
i = i+1
#print a
for j in range(p+1,N+1):
if a[j]!=0:
p=a[j]
f = 1
break
else:
f=0
if f==0:
break
for i in a:
if i!=0 and i!=1:
print i
if __name__ == '__main__':
main()
We need to build a list of prime, for that we dont need to check for each number if its prime or not. Simply check the number if its divisible by initial prime list. Your initial prime list would be {2, 3}, if number is not divisible by all the primes in list then it would be prime as well.
5 is not divisible by 2 & 3 so it's prime and now added to list. For 6 we need to check if its divisible by 2, 3 & 5. If its divisible by any of the prime its not prime.
One more optimization one can do is to ignore all even numbers.
bool IsPrime(int number, vector<int>& primeList)
{
bool isPrime = true;
for(size_t i = 0; i < primeList.size(); ++i)
{
if (number % primeList[i] == 0)
{
isPrime = false;
break;
}
}
return isPrime;
}
void PrintPrime()
{
vector<int> primeList;
int number;
primeList.push_back(2);
cout << "Enter the number : ";
cin >> number;
for (int i = 3; i < number; i+=2)
{
if (IsPrime(i, primeList))
{
primeList.push_back(i);
}
}
for(size_t i = 0; i < primeList.size(); ++i)
{
cout << primeList[i] <<",";
}
}
class PrimeNumber {
public static void main(String[] args) {
int numberOfPrimes = 125;
for (int i = 2; i < Integer.MAX_VALUE; i++) {
if (isPrime(i)) {
numberOfPrimes--;
System.out.println(i);
}
if (numberOfPrimes == 0) {
break;
}
}
}
static boolean isPrime(int n) {
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
import java.util.ArrayList;
public class A2 {
private static ArrayList<Integer> primes(int n) {
boolean[] notPrime = new boolean[n + 1];
notPrime[0] = notPrime[1] = true;
ArrayList<Integer> results = new ArrayList<Integer>();
for (int i = 2; i < n; i++) {
if (notPrime[i] == false) {
results.add(i);
for (int j = i * i; j < n; j += i) {
notPrime[j] = true;
}
}
}
return results;
}
public static void main(String[] args) {
System.out.println(primes(100));
}
}
could be something like this?
void Prime::runPrimes_toN()
{
//common prime divisors
//2,3,5,7
static const int arr[4] = { 2, 3, 5, 7 };
//generate primes from 2 to N
std::vector<int> primes;
for (int i = 2; i <= this->n; i++) {
bool isPrime = 1;
for (auto&& p : arr) {
//if no remainder and counter not = divisor
//not prime
if ((i % p == 0) && (i != p)) {
isPrime = 0;
}
}
if (isPrime == 1) {
primes.push_back(i);
}
}
for (auto&& c : primes) {
std::cout << c << std::endl;
}
}
//Java class
- css March 31, 2011class TestPrimes{
public static void printPrimes(int n){
if ( n <= 1)
return;
in all[] = new int[n+1];
for (int i = 0; i <= n; i++){
all[i] = i;
}
int prime[] = new int[n+1];
for (int i = 0; i <= n; i++)
prime[i] = 1;
int x = 2;
while (x <= n){
if (prime[x] == 1){
System.out.println(x);
for (int j = 1; j * x <=n; j++)
prime[j*x] = 0;
}
x++;
}
}
}