CODEWITHSUNDEEP
java
Sam Smith
Sam Smith

Reputation: 21

how to use arraylist method for another method?

I am supposed to find and return the kth element in a sequence of prime numbers. for example if k=5 then the 5th prime number is 11. (2, 3, 5, 7, 11, 13, 17, 19, 23...). I am also trying to pass a tester.

I was able to make the list method and the kthPrime method but I do not understand how to use them together. My kthPrime method is very very slow when the tester runs and is failing.

To speed up the process we are supposed to use an arraylist to store the sequence of prime numbers generated (need to find within 1 min).

import java.util.*;
import java.util.ArrayList;

 public class Primes {
  
  public static boolean isPrime(int n) {

    if (n <= 1) 
        return false; 

    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 

    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
            
    return true; 
    
}
    
private static ArrayList<Integer> list(int x) {
    ArrayList list = new ArrayList<String>();
     for (int i = 0 ; i < 100000 ; i++) {
         if(isPrime(i) == true)
         list.add(i);
   }
return list;
}

public static int kthPrime(int k){
int max = 100000000;
int i;
int counter=1;
for (i = 0 ; i <=max ; i++){
    
    if (isPrime(i) == true){
        counter++;
        if(counter > k)
            break;
    }
}
return i;
}


public static void main(String args[]){

    int k;
    Scanner input = new Scanner(System.in);
    System.out.println("Enter k");
    k = input.nextInt();
    System.out.println("kth prime = "+Primes.kthPrime(k));
    System.out.println("primelist = "+Primes.list(k));
   }
  }

Tester:

 import static org.junit.Assert.*;
 import org.junit.After;
 import org.junit.Before;
 import org.junit.Test;

 import java.io.*;
 import java.util.*;
 import java.util.zip.CRC32;

public class PrimesTest {

@Test public void isPrimeTest() {
    CRC32 check = new CRC32();
    for(int k = 0; k < 10_000_000; k++) {
        if(Primes.isPrime(k)) { check.update(k); }            
    }
    assertEquals(783904569L, check.getValue());
}

@Test public void kthPrimeTest() {
    CRC32 check = new CRC32();
    for(int k = 0; k < 30_000; k++) {
        check.update(Primes.kthPrime(k));
    }
    assertEquals(3080752681L, check.getValue());
   }
 }

Upvotes: 2

Views: 112

Answers (2)

Rohejul Islam
Rohejul Islam

Reputation: 126

You can speed up the list method by applying Sieve of Eratosthene algorithm if max limit permits. Check the algorithm from here - Sieve of Eratosthenes

 public static ArrayList<Integer> list(int n) { 
    // Create a boolean array & initialize full array as true. 
    // A value in prime[i] will finally be false if i is not a prime, else true.
    boolean prime[] = new boolean[n+1]; 
    for(int i=0;i<n;i++) 
        prime[i] = true; 
    
    for(int p = 2; p*p <=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if(prime[p] == true) 
        { 
            // Update all multiples of p 
            for(int i = p*p; i <= n; i += p) 
                prime[i] = false; 
        } 
    } 
 
    ArrayList list = new ArrayList<Integer>();
    for(int i = 2; i <= n; i++) 
    { 
        if(prime[i] == true) 
            list.add(i);// i is prime 
    }
 
   return list;
}

Upvotes: 1

John Angland
John Angland

Reputation: 456

A simple way to proceed would be to enhance the kthPrime method to also accept a list of known primes. If k is less than the length of the list, you can simply retrieve the k'th prime from the list. If it is not, you can add primes to the list until it is k long, and then retrieve the last element.

Upvotes: 0

Related Questions