Amazon Interview Question
Software Engineer / Developers<pre lang="" line="1" title="CodeMonkey55014" class="run-this">Java solution:
public int sumOfPrimes(int n) {
BitSet bitSet = new BitSet(n + 1);
bitSet.set(0, n + 1);
for (int i = 2, last = n / 2; i <= last && i > 0; i = bitSet.nextSetBit(i + 1)) {
for (int j = i + i; j <= bitSet.length(); j += i) {
bitSet.clear(j);
}
}
System.out.println(bitSet.toString()); // Print all primes from 1 up to n
int sum = 0;
int index = 0;
while ((index = bitSet.nextSetBit(++index)) > 0) {
sum += index;
}
System.out.println(sum);
}</pre>
<pre lang="" line="1" title="CodeMonkey26398" class="run-this">Java solution:
public int sumOfPrimes(int n) {
BitSet bitSet = new BitSet(n + 1); // one extra bit to save many -1 operations
bitSet.set(1, n);
for (int i = 2, last = n / 2; i <= last && i > 0; i = bitSet.nextSetBit(i + 1)) {
for (int j = i + i; j <= bitSet.length(); j += i) {
bitSet.clear(j);
}
}
System.out.println(bitSet.toString()); // Print all primes from 1 up to n
int sum = 0;
int index = 0;
while ((index = bitSet.nextSetBit(++index)) > 0) {
sum += index;
}
System.out.println(sum);
}</pre>
Thanks! That helps:)
For the implementation, you can use an array[0,n-1]. The index will map to the prime number, and the content array[i] will be 0 and 1, which indicates if it is a prime or not.
#include<stdio.h>
int main()
{
int i,j;
Read n;
for (i=2; i<n; i++)
{
j=2;
while(j<i)
{
if(i%j==0)
break;
j++;
}
if(j==i)
printf("%d ",i);
}
return 0;
}
Java code to find out prime number:
public class PrimeNumber
{
public static void main(String args[]){
int i,j;
System.out.println("Enter Prime Number range");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = br.read();
for (i=2; i<n; i++)
{
j=2;
while(j<i)
{
if(i%j==0)
break;
j++;
}
if(j==i)
System.out.println(i);
}
}
}
public class ArithmaticOperation {
public static void main(String[] args) {
int num = 4;
primeNumber(num);
}
private static void primeNumber(int num) {
boolean bNotPrime = false;
if(num==2 || num==3 || num==5){
System.out.println(num + " is a prime number...");
return;
}
for(int i=2;i<=num/2;i++){
if(num%i == 0)
bNotPrime = true;
}
if(!bNotPrime)
System.out.println(num + " is a prime number...");
else
System.out.println(num + " is NOT a prime number...");
}
}
SieveOfEathonse
namespace PrimeNumbersListSieveOfEathonse
{
class Program
{
private static int upperLimit = 10000;
private static Boolean[] flags;
static void Main(string[] args)
{
findPrimes(upperLimit);
displayPrimes();
Console.ReadKey();
}
private static void findPrimes(int number)
{
int upperLimit = number;
flags = new Boolean[upperLimit + 1];
for (int position = 0; position <= upperLimit; position++)
{
flags[position] = false;
}
for (int position = 2; position <= Math.Sqrt(upperLimit); position++)
{
if (!flags[position])
{
int multiple = position * 2;
while (multiple <= upperLimit)
{
flags[multiple] = true;
multiple += position;
}
}
}
}
private static void displayPrimes() {
for (int position = 2; position <= upperLimit; position++) {
if (!flags[position]) {
Console.WriteLine(position + ", ");
}
}
}
}
}
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class PrimeTest2 {
/**
* @param args
*/
public static void main(String[] args) {
int count=0, p, numberOfPrimes;
List<Integer> primeList = new LinkedList<Integer>();
System.out.print("Enter the number of primes you want to get: ");
Scanner scan = new Scanner(System.in);
while(true){
if(!scan.hasNextInt()){
System.out.print("please enter only integer: ");
scan.next();
continue;
}else{
numberOfPrimes = scan.nextInt();
break;
}
}
p=1;
while(count<numberOfPrimes){
if(checkPrime(p)){
primeList.add(p);
count++;
}
p++;
}
System.out.println("First "+numberOfPrimes+" primes: "+primeList);
}
public static boolean checkPrime(int x){
if(x==1 || x ==2) return true;
if(x%2==0) return false;
int k=3;
int a=x/k+x%k;
while(k<=a){
if(x%k==0){
return false;
}else{
k+=2;
a = x/k+x%k;
}
}
return true;
}
}
void PrintPrimeNo(int n)
- kms April 20, 2011{
int i,l;
double j,k;
bool primeNo;
for(i=1; i<=n;i++)
{
primeNo = true;
j=2; k=1.0*i/2;
while(j<=k)
{
l = (int)k;
if((k - (double)l) == 0)
{
primeNo = false;
break;
}
else
{
j++;
k = 1.0*i/j;
}
}
if(primeNo)
cout << i << " ";
}
}