hard stuck

[John3682]

hey zapshe tysm for responding

i replaced ur code with mine but i still getting the same result

i think if the N is bigger than 400 it either shows a random thing , number is minus or just shows nothing it wont even end if i enter 1000 for n and i think there are 2 inputs (i dont know the numbers ) that suppose to cout numbers like this :


input:

1
1000000000

output :

999999941999999673/1999999887999999118

[John3682]

i know my code is super shit and i used too many loops and ... but i was focusing on the algorithm , now that i know the math part works im stuck with this

it cant handle a number (N) bigger than 400 also it needs to cout a 18 digit number


i think one of the parts that takes the most time is where it calculates GCD AND LCM

like if a fraction is : 1/2 + 1/6 = 3/6 or 1/6 + 1/15 = 7/30

[zapshe]

If the number is negative, then replace the integer you're using with unsigned long int

Now that you have the math working, think about how to make the math more expedient.

With your GCD and LCM functions I don't think they're the problem. You can use the built in STL to avoid the extra function:

https://www.geeksforgeeks.org/stdgcd-c-inbuilt-function-finding-gcd/

It find the GCD using the same method you coded.

Also, keep the change I showed you. Getting your program to run faster means making it more efficient everywhere.


The biggest issue is that the purpose of what you're code is trying to do is vague, so it's hard to see what can be cut out or changed.

[jonnin]

can you post the latest version that works?

[John3682]

i replaced every int with unsigned long int and now it wont even show any error or that it has ended or anything , just shows the numbers i entered like if i enter : 1 and for the n 50 it shows :

1
50

-

and nothing else

[jonnin]

I did that and get
1
50
2393/4982

had to fix main … main still returns 'int' or is error.

consider:

bool isPrime(uint64_t N)
{	
	if( gcd(N,9542956417351352526ULL) != 1) return false;
	//this is like your check but it covers 1 to 73.  
	for (uint64_t i = 5; i * i <= N; i = i + 6)
		if (N % i == 0 || N % (i + 2) == 0)
			return false;
	return true;
}

[John3682]

im so sorry , i mean 500 , it cant calculate higher than 400 :

#include <iostream> 
#include <string>  
#include <sstream>   
//--------------------------------------------------------------------
using namespace std;
//--------------------------------------------------------------------
unsigned long long 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 << "\n";
	}

	cout << buffer.str();

	return 0;
}


//--------------------------------------------------------------------
unsigned long long 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 when i replaced ur code wit mine , math wise it didnt work anymore .

[lastchance]

@John3682,
I did give you a solution:
http://www.cplusplus.com/forum/beginner/270312/#msg1164447

What was wrong with that?

[John3682]

@lastchance

i dont know what number theyre going to enter the :
5

3
6
9
10
5

are just examples of what theyre going to use and the range for N is 10^9
also i dont know how to use string stream , i need to cin up to 500 (T) like this

int T, N;

	cin >> T;

	for (int i = 1; i <= T; i++)
	{
		cin >> N;
        }

[lastchance]

Using stringstream was simply so that you could test it in cpp.sh without any great effort to input anything.


You can code it with cin >> replacing in >> - they will almost certainly be redirecting standard input from a file - nobody in their right mind is going to sit there and type in 500 input values, despite your

i need to cin up to 500 (T) like this

In my sample you can see a test with n=10⁹ - look carefully. You can also see where I used unsigned long long - in my code aliased by "INT" because "unsigned long long" is rather a mouthful.

[John3682]

ur code works PERFECT with big nums but now its math is not right

it needs to calculate this :

n
∑ 1/(v(i)*u(i)) =
i=2

but if

n+1 = prime number

, then its this :

n
∑ 1/(v(i)*u(i))= 1/2 - 1/p =
i=2

like 6 or 5 or 11 ...

my code result 50% :

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

ur code 20% :

Compiled Successfully
Test 1
WRONG ANSWER
Test 2
ACCEPTED
Test 3
WRONG ANSWER
Test 4
ACCEPTED
Test 5
WRONG ANSWER
Test 6
WRONG ANSWER
Test 7
WRONG ANSWER
Test 8
WRONG ANSWER
Test 9
WRONG ANSWER
Test 10
WRONG ANSWER

i replaced this : using INT = unsigned long long; with any int i had and i still get 50.

[John3682]

i think ur code just needs to simplify the last fraction before cout`ing it

[John3682]

i used this :

for (int i = 1; i <= denominator; i++)
{
if (numerator%i==0 && denominator%i==0)
{
numerator /= i;
denominator /= i;
}
}

for simplification and it gave me this 60 %:

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
ACCEPTED
Test 9
ACCEPTED
Test 10
ACCEPTED

[lastchance]

So, which value of n do you think gives the wrong answer? It performs perfectly well with n=6 or 5, as you will find by running it.

If you actually bother to look at the code you will see that it does simplify each fraction WHILE outputting it. What do you think the function hcf does?

Unless of course you have managed to change it whilst submitting it ...

[John3682]

yeah , u were right i missed a part , thank you so much for taking the time to help me

im completely new to this whole coding and i need to learn things that they haven't teached us yet , while answering their assignments and when i see i cant answer it or it needs knowledge that i dont have , after searching sites for hours , i see that i have no other choice but to come here .


sorry for taking ur time