|
|
вернуться в форум#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 100000000
void prime(int n)
{
int i,j,temp,count=0;
for(i=2;i<=MAX;i++)
{
temp=0;
for(j=2;j<=sqrt(i);j++)
{
if(i%j==0)
{
temp=1;
break;
}
}
if(temp==0)
{
count++;
}
if(count==n)
{
printf("%d\n",i);
break;
}
}
}
int main()
{
int n,i;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
for(i=0;i<n;i++)
{
prime(arr[i]);
}
return 0;
}
this is my code...its working perfectly fine on codeblocks...ive used two more methods 1. where in the function ive run the loop till i/2 not sqrt(i) which is also correct but i presume will take more loops and therefor less efficient code. 2. i use pointer in main functon to avoid using arrays (not sure it makes difference but still) and offcourse this code up...none of them are working below time limit even though they give correct output...any suggestions? the segment you wrote to identify if a number is prime or not is much time killing,
rather you may use this function like this:
----------------------------------------------------------------------------
bool is_prime(int n)
{
if(n < 2) return 0;
else if(n == 2) return 1;
else if(n%2 == 0) return 0;
int root = sqrt(n);
for(int i = 3; i <= root; i += 2) {
if(n % i == 0) return 0;
}
return 1;
}
----------------------------------------------------------------------------
Hints: 2 is the only even number which is prime.
then you may store prime numbers in an array.
finally the program seems to be like this... :
---------------------------------------------------------------------------
#include <iostream>
#include <cmath>
using namespace std;
bool is_prime(int n)
{
//if(n < 2) return 0;
//else if(n == 2) return 1;
//else if(n%2 == 0) return 0; // this lines aren't necessary for this program.
int root = sqrt(n);
for(int i = 3; i <= root; i += 2) {
if(n % i == 0) return 0;
}
return 1;
}
int main()
{
int k, i, n, *num, prime_num[15001] = {0, 2}; // 2 is in 1st position.
for(n = 3, i = 2; i <= 15000; n += 2)
if(is_prime(n)) prime_num[i++] = n;
cin >> k;
num = new int [k];
for(i = 0; i < k; i++) cin >> num[i];
for(i = 0; i < k; i++)
cout << prime_num[num[i]] << '\n';
delete [] num;
return 0;
}
--------------------------------------------------------------------------------- |
|
|
