## 10791 - Minimum Sum LCM

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sajid_1989
New poster
Posts: 1
Joined: Thu Nov 11, 2010 6:56 am

### Re: 10791 - Minimum Sum LCM

I am getting Runtime Error. Can't find the reason. Need help badly

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <cctype>
#include <utility>
#include <cstdlib>
#include <algorithm>
#include <bitset>

using namespace std;

#define rep(i, b) for(i = 0; i < b; i++)
#define For(i, a, b) for( i = a; i <= b; i++)
#define N 1000000
#define NN 66000
#define PI acos( -1.0 )
#define INF 2147483646
#define LL long long
#define modu 100000007

bool mark[N + 5];
vector <int> primeList;

int min(LL a, LL b)
{
if(a < b) return a;
return b;
}

LL power(int x, int y)
{
LL pro = 1;
for(int i = y; i > 0; i--)
pro *= x;

return pro;
}

void mySieve()
{
int i, j;
memset(mark, true, sizeof(mark));

mark[0] = mark[1] = false;
for(i = 4; i <= N; i += 2)  mark[i] = false;

for(i = 3; i * i <= N; i += 2)
{
if(mark[i])
{
for(j = i * i; j <= N; j += i)
mark[j] = false;
}
}

primeList.push_back(2);
for(i = 3; i < N; i += 2)
{
if(mark[i])    primeList.push_back(i);
}

// printf("%d\n", primeList.size());
//printf("%d \n", primeList[primeList.size() - 1]);
}

int main(void)
{
mySieve();

LL n;
int Case = 0;
while(scanf("%lld", &n) && n)
{
int i, j;
LL num = n;
i = 0;
LL sum = 0;
while(num != 1 && primeList[i] * primeList[i] <= num)
{
int count = 0;
while(num % primeList[i] == 0)
{
num /= primeList[i];
count++;
}
if(count != 0)
sum += power(primeList[i], count);
i++;
}
if(num == n || sum == n)
sum = n + 1;
else if(num != 1){
sum += num;
sum = min(n + 1, sum);
}

printf("Case %d: %lld\n", ++Case, sum);
}

return 0;
}
``````

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10791 - Minimum Sum LCM

Input

Code: Select all

``````1
0``````
Output

Code: Select all

``Case 1: 2``
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman