#include <stdio.h>
#include <stdlib.h>
int find_nontrivial_factor(int n)
{
int *primes
= (int *) malloc((n
+ 1) * sizeof(int)); int num_primes = 0;
int m = n;
for (int i = 2; i <= m / i; i++)
{
while (m % i == 0)
{
primes[num_primes++] = i;
m /= i;
}
}
if (m > 1)
{
primes[num_primes++] = m;
}
for (int i = 0; i < num_primes; i++)
{
if (primes[i] != 1 && primes[i] != n)
{
int factor = primes[i];
return factor;
}
}
return -1;
}
int main()
{
int n;
int factor = find_nontrivial_factor(n);
if (factor != -1)
{
printf("Mot thua so khong tam thuong cua %d la %d\n", n
, factor
); }
else
{
printf("Khong tim thay thua so khong tam thuong cua %d\n", n
); }
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCmludCBmaW5kX25vbnRyaXZpYWxfZmFjdG9yKGludCBuKQp7CiAgICBpbnQgKnByaW1lcyA9IChpbnQgKikgbWFsbG9jKChuICsgMSkgKiBzaXplb2YoaW50KSk7CiAgICBpbnQgbnVtX3ByaW1lcyA9IDA7CiAgICBpbnQgbSA9IG47CiAgICBmb3IgKGludCBpID0gMjsgaSA8PSBtIC8gaTsgaSsrKQogICAgewogICAgICAgIHdoaWxlIChtICUgaSA9PSAwKQogICAgICAgIHsKICAgICAgICAgICAgcHJpbWVzW251bV9wcmltZXMrK10gPSBpOwogICAgICAgICAgICBtIC89IGk7CiAgICAgICAgfQogICAgfQogICAgaWYgKG0gPiAxKQogICAgewogICAgICAgIHByaW1lc1tudW1fcHJpbWVzKytdID0gbTsKICAgIH0KCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG51bV9wcmltZXM7IGkrKykKICAgIHsKICAgICAgICBpZiAocHJpbWVzW2ldICE9IDEgJiYgcHJpbWVzW2ldICE9IG4pCiAgICAgICAgewogICAgICAgICAgICBpbnQgZmFjdG9yID0gcHJpbWVzW2ldOwogICAgICAgICAgICBmcmVlKHByaW1lcyk7CiAgICAgICAgICAgIHJldHVybiBmYWN0b3I7CiAgICAgICAgfQogICAgfQogICAgZnJlZShwcmltZXMpOwogICAgcmV0dXJuIC0xOyAKfQoKaW50IG1haW4oKQp7CiAgICBpbnQgbjsKICAgIHByaW50ZigiTmhhcCBnaWEgdHJpIG46ICIpOwogICAgc2NhbmYoIiVkIiwgJm4pOwoKICAgIGludCBmYWN0b3IgPSBmaW5kX25vbnRyaXZpYWxfZmFjdG9yKG4pOwogICAgaWYgKGZhY3RvciAhPSAtMSkKICAgIHsKICAgICAgICBwcmludGYoIk1vdCB0aHVhIHNvIGtob25nIHRhbSB0aHVvbmcgY3VhICVkIGxhICVkXG4iLCBuLCBmYWN0b3IpOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIHByaW50ZigiS2hvbmcgdGltIHRoYXkgdGh1YSBzbyBraG9uZyB0YW0gdGh1b25nIGN1YSAlZFxuIiwgbik7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0=