CODEWITHSUNDEEP
c++prime-factoring
LoveOfLearning
LoveOfLearning

Reputation: 215

Prime factor in c++ code does not work for all inputs

This code, I supposed, would give me the largest prime factor for composite number input. However, it works for some inputs and doesn't for others.

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
int num=1, sum, count=0, test;
cin>>test;
while(num<=(sqrt(test)))
{
    if(test%num==0)
    {
        for (int prime=2; num>prime; prime++)
        {
            if(num%prime==0)
            count ++;
        }
        if (count == 0)
            sum=num;
    }
    num++;
}
cout<<sum;
}

Examples for where it does not work:

input: 6, expected: 3, got: 2;

input: 540, expected: 5, got: 3;

input: 600, expected: 5, got: 3;

Can somebody tell me what to change?

Upvotes: 0

Views: 58

Answers (3)

Ph03n1x
Ph03n1x

Reputation: 844

Bit late but still:

  int main() {
  auto num = 1;
  auto sum = 0;
  auto count = 0;
  auto test = 0;

  std::cin >> test;

  while (num <= test / 2) {
    count = 0;
    if (test % num == 0) {
      for (auto prime = 2; num > prime; prime++) {
        if (num % prime == 0) count++;
      }
      if (count == 0) sum = num;
    }
    num++;
  }
  std::cout << sum;
}

You can use auto. Also as a general tip: don't use "using namespace std". Getting used to writing std:: will save you some trouble, when working in bigger projects.

Upvotes: 0

ivan kuklin
ivan kuklin

Reputation: 140

You must add

count = 0

after

if (count == 0) sum = num;

Also when input number is prime then largest prime divisor is input number itself. In this case variable sum never inited. Init it in begin of programm to 0 and after while loop add

if (sum == 0) sum = test;

Upvotes: 2

happydave
happydave

Reputation: 7187

If you want the largest prime factor, you need to check all the way to test/2. E.g. For 38, you'll currently only check up to 6, and miss 19.

Also, you need to rest count after each test.

Upvotes: 2

Related Questions