N-th Prime


This is a companion discussion topic for the original entry at https://toph.co/p/n-th-prime

why this is given:

sympy is an external module and thus is not supported by Toph.
You can use standard library functions and standard modules only.
It is the same for any other online judges.

1 Like

I am getting RE in the 3rd case can someone please tell me what might be the reason?

Thanks

@hjr265 my Python 3 code is not being accepted. Runtime for python should be increased 3x.

1 Like

Thanks, my Python3 submission has been accepted.

1 Like

@hjr265
I think the runtime for Python should be 5x
I have optimized my python code very much but even then it took nearly 3s to run it. Then if a noob coder try to implement sieve here, how can he/she do it?
Thus the runtime should be 5x.

@touhidur
i’m getting WA on test 3.can u help?

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	ll n;cin>>n;vector<int> ans;
	vector<int> ls(500000,1);ls[1]=0;
	for(int i=1;i*i<=500000;++i){
	  if(ls[i]!=0){
		  for(int u=2;i*u<500000;u++) ls[i*u]=0;
	  }}
	  for(int i=1;i<500000;++i){
	  if(ls[i]==1) ans.push_back(i);}
	cout<<ans[n-1];
return 0;
}

@EmONIIT11
Initializing vector like this often fails (for me).
Try memset instead.

1 Like

here is my code i got WA in 3rd case what’s the problem can anyone explain???

#include<stdio.h>
int main()
{
    long long n,i,count=0,flag;
   while(scanf("%lld",&n)!=EOF){
        flag=0;
    for(i=1;i<=5000000;i++){
        flag=0;
       if(i==2||i==3||i==5||i==7||i==11||i==13)flag=0;
  else if(i%2==0||i%3==0||i%4==0||i%5==0||i%6==0||i%7==0||i%8==0||i%9==0||i%11==0||i%13==0||i==1||i==0)
            {
                flag=1;
            }
           
        if(flag==0)
        {
                count++;
                }
        if(count==n)
        {
                printf("%lld\n",i);
            break;
        }
            }
        count=0;}
    return 0;
}

My solution takes 0.6s with the sieve of Erathostenes in Python. You’re probably missing something.

Use that for this problem first.

#include<stdio.h>
int prime_nth(int n)
{
int a,i,co=0,b=0;

for(i=2; i>0; i++)
{
    b=0;
    for(a=2; a<i; a++)
    {
        if(i%a==0)
        {
            b=1;
            break;
        }

    }
    if(b==0)
    {
        co++;
    }
    if(co==n)
    {
        printf("%d",i);
        return 0;
    }}}

int main()
{int n;
scanf("%d",&n);
prime_nth(n);

    return 0;

}
…What is the problem with this program…I got wrong answer in 3rd case…plz solve this.

please help me 3rd case worng…

def nth_prime_number(n):
prime_list = [2]
num = 3
while len(prime_list) < n:
for p in prime_list:
if num % p == 0:
break
else:
prime_list.append(num)
num += 2
return prime_list[-1]

n = int(input())
print(nth_prime_number(n))

it is also my problem…if anyone can…please help me.

My code works to print nth prime but it seems memory limit exceeded :frowning:

n = int(input())
r = (n+1)**2
nth = n - 1
d = [x for x in range(2, r)]
non_prime = []
for i in range(2, r):
	for x in d:
		if i % x == 0 and x != 1 and x != i:
			non_prime.append(i)


non_prime = list(set(non_prime))
prime_numbers = [x for x in d if x not in non_prime]
print(prime_numbers[nth])

orpita i have already solved this problem . How can I help you?

you have to make the code more efficient

Thanks for replying :blush:accually in my code, it seems memory limit exceeded :slightly_frowning_face:

Many people are having problem with this problem. Here is my simple solution.

#include<bits/stdc++.h>
using namespace std;
const int n=1e7;      //0=is prime.
bool isPrime[n];      //1= is not prime. In a global variable, every element=0 by default
int main()
{
  int k,counter=1;
  cin>>k;
  for (int i=3; i*i<=n; i+=2) //Loop running through only odd numbers
  {
    if (!isPrime[i])
    {
      for (int j=i*i; j<=n; j+=i)
      {
        isPrime[j]=1;
      }
    }
  }
  for (int i=3; i<=n; i+=2) //Loop running through only odd numbers
  {
    if (k==1) {cout<<2; break;}
    if (!isPrime[i])
    {
      counter++;
      if (k==counter) {cout<<i<<'\n'; break;}
    }
  }


  return 0;
}