hard stuck

[John3682]

hey
there`s an assignments that they gave us but its more math than coding :

Write a program that calculates and prints the result of the following series:

n
∑ 1/v(i)*u(i)
i=2
​
Note that v (i) is the largest prime number smaller than (i) and u (i) is the smallest prime number greater than (i) :

v(i)<= i <u(i)

You should use a function called calculate in your program. This function receives n from its caller and returns the sum fraction as output to its caller.


hint : if n+1=p and p is a prime number :
n
∑ 1/v(i)*u(i)= 1/2 - 1/p
i=2

input :

The first line, T, specifies the number of series required. The next T line, each line contains an integer n.

1<= T <=500
2<= n <=10^9


input :

5
3
6
9
10
5

output :

7/30
5/14
61/154
9/22
23/70


input 2 :

1
1000000000

output 2 :

999999941999999673/1999999887999999118


TY in advance

***update still stuck

[TheToaster]

No problem. Here's what you have to do:

Write a program that calculates and prints the result of the following series:

n
∑ 1/v(i)*u(i)
i=2
​
Note that v (i) is the largest prime number smaller than (i) and u (i) is the smallest prime number greater than (i) :

v(i)<= i <u(i)

You should use a function called calculate in your program. This function receives n from its caller and returns the sum fraction as output to its caller.


hint : if n+1=p and p is a prime number :
n
∑ 1/v(i)*u(i)= 1/2 - 1/p
i=2

input :

The first line, T, specifies the number of series required. The next T line, each line contains an integer n.

1<= T <=500
2<= n <=10^9


input :

5
3
6
9
10
5

output :

7/30
5/14
61/154
9/22
23/70


input 2 :

1
1000000000

output 2 :

999999941999999673/1999999887999999118

[markyrocks]

i'd say the first thing you need to do is write a function that figures out if a number is prime or not... im on it this is interesting to me

[John3682]

ill update the post

[markyrocks]

lol I'm trying. First i need some more information.

1. What is the input? i or n?

2. In your first posted input and output why is there 6 input numbers and only 5 output and the 5 repeats but no output value repeats?

this is my prime related functions

bool isPrime(int a) {

	if (a == 1) {
		return true;
	}
	if (a == 2) {
		return true;
	}
	if (a == 3) {
		return true;
	}
	if (a == 5) {
		return true;
	}
	if (a == 7) {
		return true;
	}
	if (!(a % 2)) {
		return false; 
	}
	if (!(a % 3)) {
		return false;
	}
	if (!(a % 5)) {
		return false;
	}
	if (!(a % 7)) {
		return false;
	}
	else { return true; }
}

int findabove(int a) {

	for (;; a++) {
		if (isPrime(a + 1)) {
			return (a + 1);
		}
	}
}

int findbelow(int a) {
	if (a < 2) {
		std::cout << "i is too small" << "\n";
		return;
	}

	for (;; a--) {
		if (isPrime(a - 1)) {
			return (a - 1);
		}

	}

}

however i'm not entirely sure this is the right path tho

[John3682]

ty again ;

first input is T it says how many n were going to enter then we enter n`s;

in the first IO , we say were going to enter 5 number and then we enter them

[John3682]

ill update the post

[John3682]

.

[markyrocks]

Im trying i just can't replicate an established result. theres only so many ways to interpret

1/v(i)*u(i)

if i do it any other way than

1/(v(i)*u(i)) it just doesn't make any sense. If I do it like 1/v(i) * u(i) i end up with results greater than one. Let me try one last thing here..

[lastchance]

#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;
using INT = unsigned long long;

//======================================================================

INT hcf( INT a, INT b ) { return b ? hcf( b, a % b ) : a; }

//======================================================================

bool isPrime( INT n )
{
        if ( n     <  2 ) return false;
   else if ( n     <  4 ) return true;
   else if ( n % 2 == 0 ) return false;

   INT imax = sqrt( n + 0.5 );
   for ( INT i = 3; i <= imax; i += 2 )
   {
      if ( n % i == 0 ) return false;
   }
   return true;
}

//======================================================================

int main()
{
   istringstream in( "6 \n"
                     "3 \n"
                     "6 \n"
                     "9 \n"
                     "10\n"
                     "5 \n"
                     "1000000000\n" );
   ostream &out = cout;

   int T, n;
   in >> T;
   while( T-- )
   {
      in >> n;
      INT p = n, q = n + 1;
      while( !isPrime(p) ) p--;
      while( !isPrime(q) ) q++;
      INT numerator   = ( p - 2 ) * q + 2 * ( n - p + 1 );
      INT denominator = 2 * p * q;
      INT fac = hcf( numerator, denominator );
      out << numerator / fac << "/" << denominator / fac << '\n';
   }
}

7/30
5/14
61/154
9/22
23/70
999999941999999673/1999999887999999118

[John3682]

updated down below

[Thomas1965]

This looks more like a codechef challenge than normal homework.

[lastchance]

1)it cant calculate big numbers like 10^9

Use unsigned long long

2)i need to store the output and cout them all at the same time

Why?

3)i probably have time limit error too
4)its need to be shorted

So, state your algorithm.
yes, it's more maths than computing.

[John3682]

but where to use unsigned long long int ?

also i have to cout them all after taking input calculate them and then cout them , if i dont do this it just going to give me errors

[John3682]

i change some of the int`s to Ulong long and it gave me this :



Severity Code Line Description Project File Suppression State Suppression State
Error C2664 95 'int calculator(int,int *,int *)': cannot convert argument 2 from 'unsigned __int64 *' to 'int *'




i dont know which part to change

also ive solved the cout part , now im stuck with long numbers ;

[jonnin]

the calculator function must also use uint64s in the parameters; you still have them as int* should be uint64_t *

this is never going to beat any kind of time competition.
you need to do your prime numbers one time and keep them, not recompute them every time you need to check if something is prime.

c++ <algorithm> has a high perforance GCD. don't reinvent it.

printsum ... use reference parameters, not pointers, in c++.

[John3682]

lets say there no time limit (which there is but just ignore it) can u do something to this code that could calculate this just by changing the variables types ? :

input:

1
1000000000

output :

999999941999999673/1999999887999999118


---------------------------------------------------------------------------

#include <iostream> 
#include <string>  
#include <sstream>   
//--------------------------------------------------------------------
using namespace std;
//--------------------------------------------------------------------
int calculator(int, int*, int*);
void printSum(int, int, int, int, int*, int*);
void printSum1(int, int, int, int, int*, int*);
//--------------------------------------------------------------------
int LargestPrime(int TheNum)
{
	int FactorCount = 0;

	for (int i = TheNum; i >= 2; --i)
	{

		for (int j = 2; j < i; ++j)
		{
			if (i % j == 0)
			{
				++FactorCount;
			}
		}

		if (FactorCount == 0)
		{
			return i;
			break;
		}

		FactorCount = 0;
	}
	return 0;
}

//--------------------------------------------------------------------
bool 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;
}
//--------------------------------------------------------------------
int nextPrime(int N)
{

	if (N <= 1)
		return 2;

	int prime = N;
	bool found = false;

	while (!found) {
		prime++;

		if (isPrime(prime))
			found = true;
	}

	return prime;
}
//--------------------------------------------------------------------


int main()
{
	int T, N;
	stringstream buffer;
	cin >> T;
	int numerator = 1, denominator = 1;
	for (int i = 1; i <= T; i++)
	{
		cin >> N;


		if (isPrime(N + 1) == true)
		{
			int numerator_1 = 1;
			int denominator_1 = 2;

			int numerator_2 = 1;
			int denominator_2 = nextPrime(N);

			printSum(numerator_1, denominator_1, numerator_2, denominator_2 , &numerator, &denominator);
		}
		else
		{
			calculator(N, &numerator, &denominator);
		}
		buffer << numerator << "/" << denominator << endl;
	}

	cout << buffer.str();

	return 0;
}


//--------------------------------------------------------------------
int calculator(int N, int* numerator, int* denominator)
{
	int NP, LP, D, NUM = 1;
	for (int i = 2; i <= N; i++)
	{
		NP = nextPrime(i);
		LP = LargestPrime(i);

		D = (LP * NP);

		if (i == 2)
		{
			*numerator = NUM;
			*denominator = D;
		}
		if (i > 2)
		{
			printSum1(NUM, D, *numerator, *denominator, numerator, denominator);
		}
	}
	return 0;
}
//--------------------------------------------------------------------
int gcd(int a, int b)
{
	if (a == 0)
		return b;
	return gcd(b % a, a);
}
//***************************************
int lcm(int a, int b)
{
	return (a * b) / gcd(a, b);
}
//***************************************
void printSum(int num1, int den1, int num2, int den2 , int* numerator, int* denominator)
{
	int lcd = lcm(den1, den2);

	num1 *= (lcd / den1);
	num2 *= (lcd / den2);

	int res_num = num1 - num2;
	*numerator = res_num;
	*denominator = lcd;
}
//--------------------------------------------------------------------
int gcd1(int a, int b)
{
	if (a == 0)
		return b;
	return gcd1(b % a, a);
}
//***************************************
int lcm1(int a, int b)
{
	return (a * b) / gcd1(a, b);
}
//***************************************
void printSum1(int num1, int den1, int num2, int den2, int* numerator, int* denominator)
{
	int lcd = lcm1(den1, den2);

	num1 *= (lcd / den1);
	num2 *= (lcd / den2);

	int res_num = num1 + num2;
	for (int i = 1; i <= lcd; i++)
	{
		if (res_num % i == 0 && lcd % i == 0)
		{
			res_num /= i;
			lcd /= i;
		}
	}
	*numerator = res_num;
	*denominator = lcd;
}
//-------------------------------------------------------------------- 

also i dont know how to work with references they havn`t teached that to us yet;

[jonnin]

references are really simple.

void foo (int &x)  //<---- & makes it a reference. 
{
   x = 3;
}

int z = 0;
foo(z); 
cout << z; //is 3.  no pointers needed. 

I can't make your code do that off the cuff, no. I haven't followed what you are doing well enough. I will look at it again later on but that isn't a 10 cent answer.

there are times when a pointer is what you need. But where possible, the less you use them the easier it will be to read, write, and debug. This is triply true in mathy code where you don't want to have to look at *x = *y * *z;

[John3682]

update :


Compiled Successfully
Test 1
ACCEPTED
Test 2
Time Limit Exceeded
Test 3
ACCEPTED
Test 4
Time Limit Exceeded
Test 5
Time Limit Exceeded
Test 6
Time Limit Exceeded
Test 7
ACCEPTED
Test 8
Time Limit Exceeded
Test 9
ACCEPTED
Test 10
ACCEPTED


even if somehow i fix the limit (which i have no idea how) its going to give me errors since its INT and when i try to change to something bigger i keep getting errors that i dont know how to fixem

[zapshe]

Half the number of times your nextPrime function loops:

int nextPrime(int N)
{

	if (N <= 1)
		return 2;

	int prime = N;
	bool found = false;

        if(N%2 == 1)
                N++;
        else
                N+=2;

	while (!found) {
		if (isPrime(prime))
			found = true;

                prime+=2;
	}

	return prime;
}