how to use arraylist method for another method?

Question

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());
   }
 }

To start with, you have a list of String instead of Integer or Long. — chrylis -cautiouslyoptimistic-
– chrylis -cautiouslyoptimistic-, Commented Jul 11, 2020 at 5:38

Rohejul Islam · Accepted Answer · 2020-07-11 06:26:54Z

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;
}

John Angland · Accepted Answer · 2020-07-11 03:58:11Z

0

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.

answered Jul 11, 2020 at 3:58

John Angland

4564 silver badges12 bronze badges

Collectives™ on Stack Overflow

how to use arraylist method for another method?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related