Prime Number

[编程题]Prime Number

热度指数：18635 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

Output the k-th prime number.

输入描述:

k≤10000

输出描述:

The k-th prime number.

示例1

输入

3
7

输出

5
17

算法知识视频讲解

Java

Stevengmk

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
// 不需要设置10000范围，代码通俗易懂
public class Main{

	public static void main(String[] args) throws IOException{
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt();
			System.out.println(kthPrime(n));
		}
	}
	
	public static int kthPrime(int n) {
		int prime = 1;
		int count = 0;
		while (count < n) {
			prime++;
			if (isPrime(prime)) {
				count++;
			}
		}
		return prime;
	}
	
	public static boolean isPrime(int n) {
		for (int i = 2; i*i <= n; i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
}

编辑于 2020-03-23 13:22:49 回复(0)

Java

LHC0512

由于不知第k个数大小，使用while和ArrayList

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        next:
        while (scanner.hasNext()){
            int k = scanner.nextInt();
            ArrayList<Integer> list = new ArrayList<>();
            int i=2;
            while (true){
                boolean flag= true;
                for (int j = 2; j*j <= i; j++) {
                    if (i%j==0){
                        flag=false;
                        break ;
                    }
                }
                if (flag) list.add(i);
                i++;
                if (list.size()==k){
                    System.out.println(list.get(k-1));
                    break next;
                }
            }
        }
    }
}

编辑于 2020-03-19 19:38:17 回复(0)

Java

AllenHua

似乎还没有Java解法，我来给出另一种思路。
运行时间：66ms
占用内存：11612k

/*
 * 输出第k个素数,比如输入3,输出5;输入7,输出17
 */

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PrimeNumber {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            // 输出第n个素数
            int n = scan.nextInt();
            int current = 2;
            int sum = 0;
            List<Integer> list = new ArrayList<>();
            for (;;) {
                if (current > 2 && current % 2 == 0) {
                    current++;
                    continue;
                }
                int a = -1;
                for (int i = 2; i <= Math.sqrt(current); i++) {
                    if (current % i == 0) {
                        a = 0;
                        break;
                    }
                }
                if (a == -1) {
                    sum++;
                    // System.out.println(current);
                    list.add(current);

                }
                if (sum == n) {
                    break;
                }
                current++;
            }
            System.out.println(list.get(list.size() - 1));
        }
    }
}

发表于 2018-04-21 15:38:59 回复(0)