找一找（斐波那契数列）

题目要求：给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y，使y=kx，其中k为大于1的整数

输入描述 :第一行输入一个n，接下来一行输入n个正整数ai

输出描述：输出符合条件个数

示例：

输入
5
1 2 3 4 5
输出
2
说明
5个数中1和2符合条件，1是后面每个数的因子，2是4的因子
备注:
1≤n,ai≤1000000

<strong>解决1：<br /></strong>

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int N = 1000005;
int cc[N];
bool can[N];
int getint()
{
    char ch=getchar();
    int res=0;
    while((ch<'0' || ch>'9') && ch!='-')
        ch=getchar();
    bool neg=0;
    if(ch=='-')
    {
        neg=1;
        ch=getchar();
    }
    while('0'<=ch && ch<='9')
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    if(neg)
        res=-res;
    return res;
}
int main()
{
    int n,i,j;
    n=getint();
    for(i=1;i<=n;i++)
    {
        int now=getint();
        cc[now]++;
    }
    int ans=0;
    for(i=1;i<N;i++)
    {
        for(j=i+i;j<N;j+=i)
        {
            if(cc[j])
                can[i]=1;
        }
    }
    for(i=1;i<N;i++)
    {
        if(can[i])
            ans+=cc[i];
    }
    cout<<ans<<endl;
    return 0;
}

<strong>解决2：</strong>

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1000001],b[2000001];
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    int sum=0;
    sort(a,a+n);
    for(i=1;i<a[n-1];i++){
        if(b[i]){
           for(int j=2;i*j<=a[n-1];j++)
            if(b[i*j])
            {sum+=b[i];break;}
        }
         
    }
    printf("%d\n",sum);
}

<br /><br />