[原]Hrbust1328 相等的最小公倍数 (筛素数,素因子分解)

2014/10/17 23:34
阅读数 12

本文出自:http://blog.csdn.net/svitter/


题意:

求解An 与 An-1是否相等。

n分为两个情况——

1.n为素数,

2.n为合数。

=  =好像说了个废话。。素数的时候,可以直接输出no,因为素数不可能和An-1相等。合数的时候,如果n是a^b次方,那么也是NO。原因很简单,之前数字的最小公倍数的n的因子次方数,不能超过n的次方数。


//============================================================================
// Name        : 数论问题.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;
#define lln long long int
#define MAXN 1000001

bool vis[MAXN];
int prime[100000];
int p;

void Prime()
{
    //0为不是合数,1为是合数
    memset(vis, 1, sizeof(vis));
    p = 0;
    int i, j;
    for(i = 2; i < MAXN; i++)
    {
        if(vis[i])
        {
            prime[p++] = i;
            for(j = 2 * i; j < MAXN; j += i)
                vis[j] = 0;
        }
        else
            continue;
    }
}

void ace(){
	//init
	Prime();
	//work point
	int t, i;
	//num
	int a;
	int num;

	cin >> t;
	while(t--){
		scanf("%d", &a);
		if(a == 2)
		{
            printf("NO\n");
            continue;
        }
		if(vis[a])
            printf("NO\n");
        else
        {
            num = 0;
            for(i = 0 ; i <= p; i++)
            {
                if(a % prime[i] == 0)
                {
                    num++;
                    while(a % prime[i] == 0)
                        a /= prime[i];
                }
                if(a == 1)
                    break;
            }
            if(num >= 2)
                printf("YES\n");
            else
                printf("NO\n");
        }
	}
}

int main() {
	ace();
	return 0;
}


作者:svitter 发表于2014-5-2 21:17:35 原文链接
阅读:207 评论:0 查看评论
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部