I am trying to calculate prime numbers, which I've already done. But I want to calculate and print ONLY the nth prime number (User input), while calculating the rest (They won't be printed) only the nth prime number will be printed.
Here's what I've written so far:
import java.util.Scanner;
/**
* Calculates the nth prime number
* @author {Zyst}
*/
public class Prime {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n,
i = 2,
x = 2;
System.out.printf("This program calculates the nth Prime number\n");
System.out.printf("Please enter the nth prime number you want to find: ");
n = input.nextInt();
for(i = 2, x = 2; i <= n; i++) {
for(x = 2; x < i; x++) {
if(i % x == 0) {
break;
}
}
if(x == i) {
System.out.printf("\n%d is prime", x);
}
}
}
}
This is the program I wrote to calculate the prime numbers from 1 to n. However, I want it to only print the nth prime number,
What I've thought of doing is making some sort of count int and ++ing it every time it finds a prime, and when the count == n then it prints out that number, but I can't quite figure out how to land it.
You are trying to do too much in the main method. You need to break this up into more manageable parts. Write a method boolean isPrime(int n) that returns true if a number is prime, and false otherwise. Then modify the main method to use isPrime.
Using Java 8 parallelStream would be faster. Below is my code for finding Nth prime number
public static Integer findNthPrimeNumber(Integer nthNumber) {
List<Integer> primeList = new ArrayList<>();
primeList.addAll(Arrays.asList(2, 3));
Integer initializer = 4;
while (primeList.size() < nthNumber) {
if (isPrime(initializer, primeList)) {
primeList.add(initializer);
}
initializer++;
}
return primeList.get(primeList.size() - 1);
}
public static Boolean isPrime(Integer input, List<Integer> primeList) {
return !(primeList.parallelStream().anyMatch(i -> input % i == 0));
}
@Test
public void findNthPrimeTest() {
Problem7 inputObj = new Problem7();
Integer methodOutput = inputObj.findNthPrimeNumber(100);
Assert.assertEquals((Integer) 541, methodOutput);
Assert.assertEquals((Integer) 104743, inputObj.findNthPrimeNumber(10001));
}
java.math.BigInteger has a nextProbablePrime() method. Whilst I'm guessing this is meant for cryptography you could use it for you work.
BigInteger prime = BigInteger.valueOf(0);
for (int i = 0; i < n; i++) {
prime = prime.nextProbablePrime();
}
System.out.println(prime.intValue());
Although many correct and detailed explanations are available. but here is my C implementation:
#include<stdio.h>
#include<conio.h>
main()
{
int pk,qd,am,no,c=0;
printf("\n Enter the Number U want to Find");
scanf("%d",&no);
for(pk=2;pk<=1000;pk++)
{
am=0;
for(qd=2;qd<=pk/2;qd++)
{
if(pk%qd==0)
{
am=1;
break;
}}
if(am==0)
c++;
if(c==no)
{
printf("%d",pk);
break;
}}
getch();
return 0;
}
This program is an efficient one. I have added one more check-in if to get the square root of a number and check is it divisible or not if it's then its not a prime number. this will solve all the problems efficiently.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T; // number of test cases
T = sc.nextInt();
long[] number = new long[T];
if(1<= T && T <= 30){
for(int i =0;i<T;i++){
number[i]=sc.nextInt(); // read all the numbers
}
for(int i =0;i<T;i++){
if(isPrime(number[i]))
System.out.println("Prime");
else
System.out.println("Not prime");
}
}
else
return;
}
// is prime or not
static boolean isPrime(long num){
if(num==1)
return false;
if(num <= 3)
return true;
if(num % 2 == 0 || num % 3 == 0 || num % (int)Math.sqrt(num) == 0)
return false;
for(int i=4;i<(int)Math.sqrt(num);i++){
if(num%i==0)
return false;
}
return true;
}
int counter = 0;
for(int i = 1; ; i++) {
if(isPrime(i)
counter++;
if(counter == userInput) {
print(i);
break;
}
}
Edit: Your prime function could use a bit of work. Here's one that I have written:
private static boolean isPrime(long n) {
if(n < 2)
return false;
for (long i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
return true;
}
Note - you only need to go up to sqrt(n) when looking at factors, hence the i * i <= n
public class prime{
public static void main(String ar[])
{
int count;
int no=0;
for(int i=0;i<1000;i++){
count=0;
for(int j=1;j<=i;j++){
if(i%j==0){
count++;
}
}
if(count==2){
no++;
if(no==Integer.parseInt(ar[0])){
System.out.println(no+"\t"+i+"\t") ;
}
}
}
}
}
An another solution
import java.util.Scanner;
public class Prime {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] arr = new int[10000000];
for(int i=2;i<10000000;i++)
{
arr[i]=i;
}
for(int i=2;i<10000000;i++)
for(int j=i+i;j<10000000;j+=i)
arr[j]=0;
int t = in.nextInt();
for(int a0 = 0; a0 < t; a0++){
int n = in.nextInt();
int count=0;
for(int j=2;j<10000000;j++)
{
if(arr[j]!=0)
{
count++;
if(count==n)
{
System.out.println(j);
break;
}
}
}
}
}
}
Hope this will help for larger numbers...
I can see that you have received many correct answers and very detailed one. I believe you are not testing it for very large prime numbers. And your only concern is to avoid printing intermediary prime number by your program.
A tiny change your program will do the trick.
Keep your logic same way and just pull out the print statement outside of loop. Break outer loop after n prime numbers.
import java.util.Scanner;
/**
* Calculates the nth prime number
* @author {Zyst}
*/
public class Prime {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n,
i = 2,
x = 2;
System.out.printf("This program calculates the nth Prime number\n");
System.out.printf("Please enter the nth prime number you want to find:");
n = input.nextInt();
for(i = 2, x = 2; n > 0; i++) {
for(x = 2; x < i; x++) {
if(i % x == 0) {
break;
}
}
if(x == i) {
n--;
}
}
System.out.printf("\n%d is prime", x);
}
}
I just added the missing lines in your own thought process.
static int nthPrimeFinder(int n) {
int counter = 1; // For 1 and 2. assuming n is not 1 or 2.
int i = 2;
int x = 2;
int tempLength = n;
while (counter <= n) {
for (; i <= tempLength; i++) {
for (x = 2; x < i; x++) {
if (i % x == 0) {
break;
}
}
if (x == i && counter < n) {
//System.out.printf("\n%d is prime", x);
counter++;
if (counter == n) {
System.out.printf("\n%d is prime", x);
return counter;
}
}
}
tempLength = tempLength+n;
}
return 0;
}
Source: Stackoverflow.com