Epic Systems Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
package epic;
import java.text.BreakIterator;
public class Goldbach {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Goldback");
int check_value = 100;
int i;
if(check_value%2 != 0){
System.out.println("Invalid input");
}
else{
for(i=3; i<check_value/2; i=i+2){
if(isPrime(i) && isPrime(check_value-i)){
System.out.println("Goldbach of "+ check_value +"= "+ i + " && "+(check_value-i));
}
}
}
}
public static boolean isPrime(int n){
int i;
boolean flag=false;
if(n%2 == 0){
return false;
}
for(i=3; i<Math.sqrt(n); i=i+2){
if(n%i ==0){
return false;
}
}
//System.out.println("Prime num="+n);
return true;
}
}
This is good, but if the task were to print all possible sums of primes, then the fact that you omit 2 as a prime number will not yield all possible solutions for the case when n = 4 (so we won't see 2 + 2). But this is only an issue when n is 4, because for any larger number than 4 if you subtract 2, the result will be an even number larger than 2, so it wouldn't matter anyway.
public class GoldbachConjecture{
public static void getGoldbachNumbers(int number){
if(number%2 != 0)
{
System.out.println("Please enter an even number.Invalid Input");
return;
}
for(int i=0;i<number/2;i++){
if(isPrime(i) && isPrime(number-i))
System.out.println("Goldbach numbers are :"+i+" and "+(number -i)+" for "+number);
}
}
public static boolean isPrime(int number){
for(int i=2;i<number;i++){
if(number%i == 0)
return false;
}
return true;
}
public static void main(String[] args){
getGoldbachNumbers(Integer.parseInt(args[0]));
}
}
Only need to check from 2 up to sqrt(number) to determine if number is a prime. If sqrt(number) is not whole then round up to the nearest whole number.
public static void printPrimePair(int no){
//find all the primes eratosthenes algo
Boolean [] isPrime = new Boolean[no+1];
for(int i=0;i<no;i++){
isPrime[i]= true;
}
Set<Integer> primeSet = new HashSet<Integer>();
for(int i=2;i*i<no;i++){
if(isPrime[i]){
for(int j=i;j*i<no;j++){
isPrime[j*i] = false;
}
}
}
for(int i=2;i<no;i++){
if(isPrime[i])
primeSet.add(i);
}
//get the goldbach's conjucture
for(Integer i:primeSet){
if(primeSet.contains(no-i)){
System.out.println("the pair :"+i+" "+(no-i));
break;
}
}
}
bool is_prime(int n){
if (n<=1) return 0;
int m=floor(sqrt(n)+0.5);
for (int i=2; i<m; i++){
if (m%1==0) return 0;}
}
return 1;
}
package practice;
import java.util.*;
public class printassumofprime {
public static void main(String[] args) {
Scanner s= new Scanner(System.in);
System.out.println("Enter a integer");
int input = s.nextInt();
printAsSumOfPrimes(input);
}
static void printAsSumOfPrimes(int input)
{
if(input <2)
{
System.out.println("Input is less than 2");
return;
}
if(input%2!=0)
{
System.out.println("Input is not divisible by 2");
return;
}
Set<Integer> primenumbers = new HashSet<Integer>();
for(int i=2;i<input;i++)
{
boolean b=true;
for(int j=2;j<i;j++)
{
if(i%j==0)
{
b=false;
break;
}
}
if(b)
primenumbers.add(i);
}
for(int i =input -1;(i>=input/2);i--)
{
if(primenumbers.contains(i) && primenumbers.contains(input - i))
{
System.out.println(input + "="+i+"+"+(input-i));
}
}
}
}
public class epic3 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int n = 20;
int prime[] = new int[1000];
preprocess(prime,n);
for(int i = 0;i<n/2;i++){
if(prime[i] == 0 && prime[n-i] == 0){
System.out.println(i + " " + (n-i)); break;}
}
}
private static void preprocess(int[] prime, int n) {
// TODO Auto-generated method stub
prime[0] = 1;prime[1] = 1;
for(int i = 2;i<n;i++){
if(prime[i] == 0)
for(int j = i*i;j<n && j > 0;j+=i){
prime[j] = 1;
}
}
}
}
#Goldbach
def Goldbach(n,s):
if n< 4 or n%2 != 0:
return 0,0
for i in s:
if (n-i) in s:
return i, n-i
return 0,0
def findPrimes(s,n):
for i in range(3,n,2):
if i >= n:
return
if isPrime(i):
s.add(i)
def isPrime(n):
for i in range(3, int(n**0.5), 2):
if n%i == 0:
return False
return True
def main():
n=44444
s = {2}
findPrimes(s,n)
print(Goldbach(n,s))
if __name__ == '__main__':
main()
package main
import (
"fmt"
"math"
)
func findPrimes(n int, m map[int]int) {
for i:=3; i< n; i+=2 {
if isPrime(i) {
m[i] = 1
}
}
}
func isPrime(n int) bool {
for i:= 3; i <= int(math.Sqrt(float64(n))); i+=2 {
if n%i == 0 {
return false
}
}
return true
}
func GoldBach(n int, m map[int]int) (x, y int) {
if n < 4 || n%2 != 0 {
return 0,0
}
for k := range m {
if m[n-k] == 1 {
return k, n-k
}
}
return 0,0
}
func main(){
n := 44444
m := make(map[int]int)
m[2] = 1
findPrimes(n,m)
fmt.Println(GoldBach(n,m))
}
public static void printPrimePair(int no){
//find all the primes eratosthenes algo
Boolean [] isPrime = new Boolean[no+1];
for(int i=0;i<no;i++){
isPrime[i]= true;
}
Set<Integer> primeSet = new HashSet<Integer>();
for(int i=2;i*i<no;i++){
if(isPrime[i]){
for(int j=i;j*i<n;j++){
isPrime[j*i] = false;
}
}
}
for(int i=2;i<no;i++){
if(isPrime[i])
primeSet.add(i);
}
//get the goldbach's conjucture
for(Integer i:primeSet){
if(primeSet.contains(no-i)){
System.out.prinln("the pair :"+i+" "+no-i);
}
}
}
package p1;
import java.util.HashMap;
public class GoldbachConjecture {
public static void main(String args[])
{
primepair(6);
}
static void primepair(int num)
{ int c=0;
int n=num;
boolean b=true;
HashMap<Integer, Integer> l=new HashMap();
if(n%2==0 && n>2)
{
for(int i=1;i<n;i++)
{ int m=0;
if(isprime(i)&&isprime(n-i)&& m==0)
{
System.out.println(i+" "+(n-i));
m=1;
}
}
}
}
static boolean isprime(int number)
{ int v=0;
int p=number;
boolean b=false;
for(int j=2;j<=p/2;j++)
{
if(p%j==0)
{
b=true;
}
}
if(b){
return false;}
else{ return true;}
}
}
'''
Goldbach's conjecture : Every even integer greater than 2 can be expressed as the sum of two primes.
Write a function which takes a number as input, verify if is an even number greater than 2 and also print atleast one pair of prime numbers.
'''
def goldbach(n):
if (n > 2 and n % 2 == 0):
for i in range(2,n/2):
if is_prime(i) and is_prime(n-i):
return (i,n-i)
return None
def is_prime(n):
for i in range(2,n/2):
if n % i == 0:
return False
return True
print (goldbach(100)) # 3,97
print (goldbach(114)) # 5, 109
print (goldbach(32)) # 3, 29
print (goldbach(2)) # None
for i in range(2,n/2): -> (2,n/2+1)
Think about 6, range(2,3) only check for 2 not 3. Then you miss 6 because it can be divided by two 3s, which are all prime numbers.
A little bit improvement, where we can create prime dictionary to avoid checking already found prime numbers.
primes = {}
def gold_bach(number):
if number%2!=0 or number<=2:
print "Not even or not greater than 2"
for i in range(2, number/2+1):
if primes.has_key(i) and primes.has_key(number-i):
return i, number-i
elif prime(i) and prime(number-i):
primes[i] = 1
primes[number-i] = 1
return i, number-i
import java.util.*;
public class Goldbachs {
public static void getTwoPrimes(ArrayList<Integer> primes, int number)
{
int sum = number;
for(int i = 0, j = primes.size()-1;i<=j;)
{
if(primes.get(i)+primes.get(j)==sum)
{
System.out.println("Numbers are: "+primes.get(i)+" and "+primes.get(j));
return;
}
if(primes.get(i)+primes.get(j)<sum)
{
i++;
}
if(primes.get(i)+primes.get(j)>sum)
{
j--;
}
}
}
public static void main(String args[]){
ArrayList<Integer> primes = new ArrayList<Integer>();
primes.add(2);
primes.add(3);
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number");
int number = Integer.parseInt(sc.next());
if(number>2)
{
if(number%2==0)
System.out.println("Even number");
else
System.out.println("Wrong input");
}
else
{
System.out.println("Wrong input");
}
int count = 0;
for(int i =5;i<number;i=i+2)
{
for(int j = 0; j< primes.size(); j++)
{
if(i%primes.get(j)==0)
{
count++;
}
}
if(count==0)
{
primes.add(i);
}
count=0;
}
System.out.println(primes);
getTwoPrimes(primes, number);
}
}
import java.util.*;
public class Goldbachs {
public static void getTwoPrimes(ArrayList<Integer> primes, int number)
{
int sum = number;
for(int i = 0, j = primes.size()-1;i<=j;)
{
if(primes.get(i)+primes.get(j)==sum)
{
System.out.println("Numbers are: "+primes.get(i)+" and "+primes.get(j));
return;
}
if(primes.get(i)+primes.get(j)<sum)
{
i++;
}
if(primes.get(i)+primes.get(j)>sum)
{
j--;
}
}
}
public static void main(String args[]){
ArrayList<Integer> primes = new ArrayList<Integer>();
primes.add(2);
primes.add(3);
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number");
int number = Integer.parseInt(sc.next());
if(number>2)
{
if(number%2==0)
System.out.println("Even number");
else
System.out.println("Wrong input");
}
else
{
System.out.println("Wrong input");
}
int count = 0;
for(int i =5;i<number;i=i+2)
{
for(int j = 0; j< primes.size(); j++)
{
if(i%primes.get(j)==0)
{
count++;
}
}
if(count==0)
{
primes.add(i);
}
count=0;
}
System.out.println(primes);
getTwoPrimes(primes, number);
}
}
public class Solution {
public static boolean isEven(int num){
if(num<=2){
System.out.println("Number less than 3");
}
return num%2==0?true:false;
}
public static boolean isPrime(int num){
for(int i=2;i<=Math.sqrt(num);i++){
if(num%i==0){
return false;
}
}
return true;
}
public static void Goldbach(int num){
if(isEven(num)){
for(int i=2;i<=num/2;i++){
if(isPrime(i)&&isPrime(num-i)){
System.out.println("Pair"+i+","+(num-i));
}
}
}else{
System.out.println("Odd or less than 3");
}
}
public static void main(String[] args){
Goldbach(20);
}
}
public class GoldBachConjecture {
private final int check_value;
public GoldBachConjecture(final int check_value){
this.check_value=check_value;
}
public static void main (String args[])
{
GoldBachConjecture goldObj= new GoldBachConjecture(100);
System.out.println("");
goldObj.findPair();
}
private void findPair() {
if(check_value%2!=0){
System.out.println("Invalid input");
}
for(int i=3;i<check_value/2;i+=2){
if(isPrime(i) && isPrime(check_value-i)){
System.out.println("Goldbach of "+ check_value +"= "+ i + " && "+(check_value-i));
}
}
}
private boolean isPrime(int n) {
if(n%2 == 0){
return false;
}
for(int i=3; i<=Math.sqrt(n); i=i+2){
if(n%i ==0){
return false;
}
}
return true;
}
}
#include <string>
#include <iostream>
using namespace std;
int isprime(int n){
int flag = 0;
for(int i=2; i<n; i++){
if(n%i==0){
++flag;
return flag;
}
}
return flag;
}
void goldbach(int n){
if(n<=2){
cout<<n<<" not greater than 2"<<endl;
return;
}
if(n%2!=0){
cout<<n<<" not even"<<endl;
return;
}
for(int i=1; i<((n/2)+1); i++)
{
if((isprime(i)==0) && (isprime(n-i)==0))
cout<<"goldbach pair: "<<i<<" and "<<n-i<<endl;
}
return;
}
int main()
{
goldbach(60);
return 0;
}
class Strong_GoldBach_all_possible_pairs
{
public static void main(int n)
{
if(n%2==1 || n<=2){System.out.println("invalid input");return;}
int n1=0,n2=0;
outer :for(n1=1;n1<n;n1++)
{
if(isprime(n1))
{
for(n2=0;n2<n;n2++)
{
if(isprime(n2)){ if(n1+n2==n && n1<=n2)System.out.println(n1+" + "+n2+" = "+(n1+n2));}
}
}
}
}
private static boolean isprime(long x)
{
long a;if(x==1)return false;
for(a=2;a<=Math.sqrt(x);a++)
{
if(x%a==0)
return false;
}
return true;
}
}
class Strong_GoldBach_all_possible_pairs
{
public static void main(int n)
{
if(n%2==1 || n<=2){System.out.println("invalid input");return;}
int n1=0,n2=0;
outer :for(n1=1;n1<n;n1++)
{
if(isprime(n1))
{
for(n2=0;n2<n;n2++)
{
if(isprime(n2)){ if(n1+n2==n && n1<=n2)System.out.println(n1+" + "+n2+" = "+(n1+n2));}
}
}
}
}
private static boolean isprime(long x)
{
long a;if(x==1)return false;
for(a=2;a<=Math.sqrt(x);a++)
{
if(x%a==0)
return false;
}
return true;
}
}
Based on Sieve of Eratosthenes to find out all the all the primes smaller than input number n, and traverse these primes, while a hash set to store the complementary numbers, once one valid complementary traversed, just return this pair.
- wxliuyizhe October 17, 2014