精华内容
下载资源
问答
  • 半素数

    2019-11-27 14:55:18
    半素数:给定一个自然数,请说出它的所有严格意义上的除数的和 定义:一个自然数的严格意义上的除数的和是比它自身小的除数,如20的严格意义上的除数的和为 #include<iostream> using namespace std; //...
    • 半素数:给定一个自然数,请说出它的所有严格意义上的除数的和
      定义:一个自然数的严格意义上的除数的和是比它自身小的除数,如20的严格意义上的除数的和为
    #include<iostream>
    
    using namespace std;
    //半素数:给定一个自然数,请说出它的所有严格意义上的除数的和
    //定义:一个自然数的严格意义上的除数的和是比它自身小的除数,如20的严格意义上的除数的和为1+2+4+5+10=20
    int main() {
    	int n,a,sum,j;
    	cin >> n;
    	for (int i = 0; i < n; i++) {
    		cin >> a;
    		sum = 0;
    		for (int i = 1; i < a; i++) {
    			if (a % i == 0) {
    				sum = sum + i;
    			}
    		}
    		cout << a << "的严格意义上的除数和:" << sum << endl;
    	}
    	return 0;
    }
    

    半素数

    展开全文
  • 29半素数

    2016-12-10 15:15:32
    如果一个数能分解为两个素数的乘积,且大于 1,那么,这个数就是半素数。例如,6=2×3,2 和3 都是素数,那么,6 就是半素数。12 就不是半素数。你的任务就是判断一个给定的数字是否是一个半素数。 2
    素数的定义
    素数是指大于 1,且只能被本身和1 整除的正整数(只有1 和本身两个正因子)。例如,2,11,67,89 都是素数,但8,20,27 都不是素数。
    半素数的定义
    如果一个数能分解为两个素数的乘积,且大于 1,那么,这个数就是半素数。例如,6=2×3,2 和3 都是素数,那么,6 就是半素数。12 就不是半素数。你的任务就是判断一个给定的数字是否是一个半素数。
    2.输入描述
    输入数据中有多个测试案例。每个案例只包含一个整数 N(2≤N≤1 000 000)。
    3.输出描述
    一个测试案例输出一行。如果这个数是半素数,则直接输出“Yes”,否则,输出“No”。
    4.输入样例
    3
    4
    6
    12
    5.输出样例
    No
    Yes
    Yes
    No 


    #include "stdafx.h"
    #include<iostream>
    #include<fstream>
    #include<cmath>
    #include<set>
    #include<vector>
    using namespace std;
    vector<int> v;
    set<int>s;
    void pt(int a, int b)
    {
    	for (int i = a; i <= b; i++)
    	{
    		if (i!=2&&i % 2 == 0) continue;
    		for (int j = 3; pow(j, 2) < i; j++)
    		{
    			if (i%j == 0) goto RL;
    		}
    		v.push_back(i);
    	RL:continue;
    	}
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	
    	ifstream fin("D:\\visual studio 2013 code\\test.txt");
    	//建立2-1000000之间的素数集合
    	pt(2, 100000);
    	//建立2-1000000之间的半素数集合
    	set<int>::iterator it;
    	int temp;
    	for (int i = 0; i < v.size(); i++)
    	{
    		for (int j = 0; j < v.size(); j++)
    		{
    			temp = v[i] * v[j];
    			s.insert(temp);
    		}
    	}
    	while (fin >> temp)
    	{
    		it=s.find(temp);
    		if (it != s.end())
    		{
    			cout << "YES" << endl;
    		}
    		else
    		{
    			cout << "NO" << endl;
    		}
    	}
    	
    	return 0;
    }
    


    展开全文
  • 根据半素数除数的分布特征,提出了一种可以通过并行计算找出半素数的小除数的方法。 该方法将确定性搜索与概率搜索结合在一起,需要较少的内存,并且可以在普通的多核计算机上实现。 实验表明,使用这种方法,可以在...
  • UVA-11105 H-半素数

    2019-12-26 21:24:22
    =106+1),输出h及以下有多少个H-半素数。 H-半素数的定义:能写成两个H素数的乘积的H数。 H素数的定义:本身不是1,且不能写成两个不是1的数的乘积的H数。 H数的定义:可以表示为4n+1的数,n为任意整数。 一看到...

    题目大意:

    给出一个数h(1<=h<=106+1),输出h及以下有多少个H-半素数。
    H-半素数的定义:能写成两个H素数的乘积的H数。
    H素数的定义:本身不是1,且不能写成两个不是1的数的乘积的H数。
    H数的定义:可以表示为4n+1的数,n为任意整数。

    一看到“素数”,就会想到用筛法。106+1范围的数,用筛法可以很快筛出来。筛的过程要注意:可以套用筛素数,但是要把第一个for中的i++改成i+=4,并将下限——最小的素数2——改成最小的H素数5。

    得到H素数表后,把它们打进一个vector里(数组狂可以尝试改成int hp[1000005],sz的代码)。接下来将H素数表中的数两两配对,乘起来,每一对都要这么操作,然后放到一个H-半素数表里,再统计即可。

    注意此题数据忒TM坑了,题目中说好的h是个H数,可是当我用下面代码提交时,WA了,原因竟是因为测试数据中出现了非H数

    代码如下:

    #include <iostream>
    #include <vector>
    #include <cstring>
    #include <cmath>
    #include <set>
    using namespace std;
    int vis[1000005],hsp[1000005];
    int main(){vector<int>hp;
      //make H-prime list
      for(int i=5;i<=1001;i+=4)if(!vis[i])
        for(int j=i*i;j<=1000001;j+=i)vis[j]=1;
      for(int i=5;i<=1000001;i+=4)
        if(!vis[i])hp.push_back(i);
      //make H-semi-prime list
      for(int i=0;i<hp.size();i++)
        for(int j=0;j<=i&&hp[i]*hp[j]<=1000001;j++)
          hsp[hp[i]*hp[j]]=1;
      //count H-semi-prime
      for(int i=1;i<=1000001;i+=4)hsp[i]+=hsp[i-4];
      //此处可以注意到,i+=4时把非H数跳过了
      for(int n;cin>>n&&n;)cout<<n<<' '<<hsp[n]<<endl;
      return 0;
    }
    //WA
    

    正确代码如下:

    #include <iostream>
    #include <vector>
    #include <cstring>
    #include <cmath>
    #include <set>
    using namespace std;
    int vis[1000005],hsp[1000005];
    int main(){vector<int>hp;
      //make H-prime list
      for(int i=5;i<=1001;i+=4)if(!vis[i])
        for(int j=i*i;j<=1000001;j+=i)vis[j]=1;
      for(int i=5;i<=1000001;i+=4)
        if(!vis[i])hp.push_back(i);
      //make H-semi-prime list
      for(int i=0;i<hp.size();i++)
        for(int j=0;j<=i&&hp[i]*hp[j]<=1000001;j++)
          hsp[hp[i]*hp[j]]=1;
      //count H-semi-prime
      for(int i=1;i<=1000001;i++)hsp[i]+=hsp[i-1];
      //数据有bug,上边应用如此的鲁棒形式,不能用i+=4,hsp[i]+=hsp[i-4]
      for(int n;cin>>n&&n;)cout<<n<<' '<<hsp[n]<<endl;
      return 0;
    }
    //AC
    
    展开全文
  • ACM程序设计 半素数 题目解释 思路分析 源代码 及扩展
  • zoj_2723 Semi-Prime 半素数

    千次阅读 2015-03-19 19:58:24
    题目链接:zoj_2723 Semi-Prime 半素数  又是一道有关素数的题,这回找的是半素数,即除了1和本身外,只有两个素数因子。由于数据量大(2  基本思路是建立一个[2,1000 000]范围内的半素数表,读入数据,直接检索...

    题目链接:zoj_2723 Semi-Prime 半素数

           又是一道有关素数的题,这回找的是半素数,即除了1和本身外,只有两个素数因子。由于数据量大(2<N<1000 000),所以如果将每个测试数据都做因式分解,一定会出现超时错误。

           基本思路是建立一个[2,1000 000]范围内的半素数表,读入数据,直接检索。

           为了解决这个问题,我们继续使用造福人类的STL——vector & set,分别用来存储素数和半素数。为什么素数的存储不用set呢?因为我们的终极目标不是判断素数,而是半素数。采用vector存储素数有利于线性查找,在for循环中,可直接根据下标遍历素数表。而采用set存储半素数,是因为set是平衡检索二叉树,可以将元素自动排序,检索速度最快。

           这里再复习一下素数的判断方法:首先排除2以外的所有偶数,然后从奇数中排除素数的倍数,剩下的就是素数。

           注意:一个合数的最小素因子不超过它的平方根,这个可以做循环停止的条件。


    代码:

    #include <iostream>
    #include <vector>
    #include <set>
    #include <cmath>
    using namespace std;
    vector<int> v;
    set<int> s;
    void ChoosePrime(int a,int b)//建立[a,b]范围内的素数表
    {
        for(int i=a;i<=b;i++)
        {
            //2是素数,这里清楚2的倍数
            if(i!=2&&i%2==0) continue;
            for(int j=3;j*j<=i;j+=2)
            {
                if(i%j==0) goto RL;
            }
            v.push_back(i);
        RL:continue;
        }
    }
    int main()
    {
        ChoosePrime(2,500000);//建立[2,500000]范围内的素数表
        int i,j,p;
        for(i=0;i<v.size();i++)//建立[2,1000 000]范围内的半素数表
        {
            for(j=0;j<v.size();j++)
            {
                p=v[i]*v[j];//两个素数相乘
                if(p<1000000) s.insert(p);
                else break;
            }
        }
        //读入数据,在半素数表中查找,看是否在该表中
        int n;
        set<int>::iterator it;
        while(cin>>n)
        {
            it=s.find(n);
            if(it!=s.end()) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    


    展开全文
  • set,分别用来存储素数和半素数。为什么素数的存储不用set呢?因为我们的终极目标不是判断素数,而是半素数。采用vector存储素数有利于线性查找,在for循环中,可直接根据下标遍历素数表。而采用set存储半素...
  • 题目大意是让找出100 0000以内的半素数,所谓半素数就是两个素数的积(或者说一个素数的平方); 思路如下: 1.因为数太大,如果一个一个判断很可能会超时,所以要建立半素数表利用检索找到素数; 2.100 0000以内的...
  • H-半素数是指能写成两个H素数的乘积的H数(这两个数可以相同也可以不同)。输入一个H数h(h <=1000001),输出1~h之间有多少个H-半素数。 分析: 1、筛选法求H素数。 2、再枚举求H-半素数。 #pragma comment(l....
  • 半素数问题

    千次阅读 2018-08-07 19:06:44
    如果一个大于1的整数可以分解为两个素数,则称其为一个半素数。 例如,6是一个半素数,但12不是。 你的任务只是确定一个给定的数字是否是一个半素数。 Input There are several test cases in the input. ...
  • 数学中,两个素数的乘积所得的自然数我们称之为半素数。 现在我们给定一个数N,我们想要得到小于或等于N的半素数的数目。 代码 #include &lt;bits/stdc++.h&gt; using namespace std; vector&lt;int&...
  • 题目定义了一种叫半素数的数:只要一个数能被分解成两个素数,那么这个数就是半素数。 Prime Number Definition An integer greater than one is called a prime number if its only positive divisors (factors) ...
  • 半素数的判定

    千次阅读 2018-10-07 09:50:09
    另外,合数并不一定是半素数,但半素数一定是合数。 二、判断方法(不拆分数,而选择查找数,思路很厉害了。) 题目:输入一个整数N,2,000,判断N是否为半素数。 思路:1.先求出500000以内的素数(因为最小...
  • 来源:牛客网 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 最近张老师对半素数感兴趣。半素数(semi-prime)是...比如4和10是半素数,因为4=2×...
  • vector存一下2到他平方根的素数,然后在int main里面写两个循环求出所有的半素数,存起来。然后输入一个数判断在不在半素数表里就行。 我当时做的时候。想的是,写一个判断素数的函数。里面输入一个先判断是不是素数...
  • Semi-Prime(半素数

    2017-07-06 14:17:00
    建立一个【2,500000】的素数集合,在建立一个【1,1000000】的半素数集合, set是平衡检索二叉树,检索速度足够。 #include #include #include #include #include #include #include < set...
  • 所以半素数满足半素数的只有 (1)k1=2 k2=0: p^2 (2)k1=1 k2=1: p*q for ( LL i = L ; i R ; i ++ ) { if ( vis [ i - L ] > 0 ) { LL x = i / vis [ i - L ] ; //假设p=vis[i-L] if ( x == ...
  • N=50000 a=[] end =N // 2 for num in range(2,end+1): for i in range(2,num): if (num % i) == 0: break ...最小的素数为2,所以先求出N/2以内的素数列表,再从列表两边开始向中间进行判断。
  • zju2723半素数?

    2010-10-13 15:29:00
    提交之前看了一下提示,我就知道会超时。不过,第一次在浙大提交,试试再说,然后,果不失望:超时1ms 。 用时:1001ms #include #define MAX 1000000 int num[MAX]; void getPrime() { int i,j,k;...
  • 《ACM程序设计》-Problem-R-半素数问题

    千次阅读 2017-03-19 22:48:08
    例如,2,11,67,89是素数,但8,20,27不是。 优先数定义 如果一个大于1的整数可以被分解为两个质数,则称之为质数。例如,6是质数,但12不是。 您的任务只是确定给定的数字是否是质数。 ...
  • //每次存进去的肯定是素数 a[j-l]/=i; } } } int cnt=0; for(ll i=0;i;i++) { if(a[i]>1) { vec[i].push_back(a[i]); } sort(vec[i].begin(),vec[i].end()); if(vec[i].size()==2) cnt++; } printf...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 237
精华内容 94
热门标签
关键字:

半素数