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

    千次阅读 2018-08-07 19:06:44
    如果一个大于1的整数可以分解为两个素数,则称其为一个半素数。 例如,6是一个半素数,但12不是。 你的任务只是确定一个给定的数字是否是一个半素数。 Input There are several test cases in the input. ...

    Prime Number Definition 


     An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself. For instance, 2, 11, 67, 89 are prime numbers but 8, 20, 27 are not.

    Semi-Prime Number Definition 


     An integer greater than one is called a semi-prime number if it can be decompounded to TWO prime numbers. For example, 6 is a semi-prime number but 12 is not.

    Your task is just to determinate whether a given number is a semi-prime number.

     

    素数定义

    如果一个大于1的整数只有一个正整数(因子)是一个整数,那么它就称为素数。 例如,2,11,67,89是素数,但8,20,27不是。

    半素数定义

    如果一个大于1的整数可以分解为两个素数,则称其为一个半素数。 例如,6是一个半素数,但12不是。

    你的任务只是确定一个给定的数字是否是一个半素数。

    Input

    There are several test cases in the input. Each case contains a single integer N (2 <= N <= 1,000,000)

     

    输入中有几个测试用例。 每个案例包含一个整数N(2 <= N <= 1,000,000)

    Output

    One line with a single integer for each case. If the number is a semi-prime number, then output "Yes", otherwise "No".

     

    一行每个案件都有一个整数。 如果数字是半素数,则输出“是”,否则输出“否”。

    Sample Input

    3
    4
    6
    12

    Sample Output

    No 
    Yes 
    Yes 
    No 

    AC码:

    #include<stdio.h>
    #include<string.h>
    const int maxn=1000010;
    int a[maxn];
    int sushu()
    {//打表求素数
    	memset(a,0,sizeof(a));
    	int i,j;
    	for(i=2;i<maxn;i++)
    	{
    		if(a[i]==0)
    		{
    			for(j=2;j*i<maxn;j++)
    			a[i*j]=1;
    		}
    	}
    	return a[maxn];
    }
    int main()
    {
    	int N,i;
    	sushu();
    	while(scanf("%d",&N)!=EOF)
    	{
    		int flag=0;
    		for(i=2;i<N;i++)
    		{
    			if(a[i]==0)
    			{
    				if(N%i==0)
    				if(a[N/i]==0)
    				{
    					flag=1;
    		    		break;
    				}	
    			}	
    		}
    		if(flag)
    		printf("Yes\n");
    		else
    		printf("No\n");
       }
    	return 0;
    }
    

     

    展开全文
  • 半素数的判定

    千次阅读 2018-10-07 09:50:09
    另外,合数并不一定是半素数,但半素数一定是合数。 二、判断方法(不拆分数,而选择查找数,思路很厉害了。) 题目:输入一个整数N,2,000,判断N是否为半素数。 思路:1.先求出500000以内的素数(因为最小...

    参考博客:https://blog.csdn.net/u010625743/article/details/44463519?locationNum=2&fps=1

                      https://blog.csdn.net/July_xunle/article/details/63250871   

                      https://www.cnblogs.com/yitou13/p/9086759.html

    一、半素数定义

            数学中,两个素数的乘积所得的自然数我们称之为半素数(也叫双素数,二次殆素数)开始的几个半素数是4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... 它们包含1及自己在内合共有3或4个因子。另外,合数并不一定是半素数,但半素数一定是合数。

    二、判断方法(不拆分数,而选择查找数,思路很厉害了。)

    题目:输入一个整数N,2<=N<=1000,000,判断N是否为半素数。

    思路:1.先求出500000以内的素数(因为最小的素数为2),建立素数表,共41538个

               【素数的判定首先排除2以外的所有偶数,然后从奇数中排除素数的倍数,剩下的就是素数】;

               2.对输入的每个整数N,从2开始找它的因子i,如果i和N/i都能在素数表中查找到,则N是半素数。

    具体实现:STL——vector & set,分别用来存储素数和半素数

    采用vector存储素数有利于线性查找,在for循环中,可直接根据下标遍历素数表。

    采用set存储半素数,是因为set是平衡检索二叉树,可以将元素自动排序,检索速度最快。

    #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;
        }
    }

     

          

    展开全文
  • //每次存进去的肯定是素数 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...

    题目链接:https://ac.nowcoder.com/acm/contest/637/C
    比赛时候不会写,补题的时候看了眼别人的骚代码,秒懂。
    思路:直接用vector存区间[l,r]之间每个数筛出来的因数,最后判一下就行了。不过这个题大佬说直接区间筛就可以了,注意数据类型开成long long就行。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define maxx 100010
    ll l,r;
    vector<ll>vec[maxx];
    ll a[maxx];
    int main()
    {
         scanf("%lld%lld",&l,&r);
         for(ll i=l;i<=r;i++)
         {
              a[i-l]=i;//要剪掉l前面的,不然存不下的
         }
         for(ll i=2;i*i<=r;i++)
         {
              for(ll j=((i+l-1)/i)*i;j<=r;j+=i)
              {
                  while(a[j-l]%i==0)
                  {
                      vec[j-l].push_back(i);//每次存进去的肯定是素数
                      a[j-l]/=i;
                  }
              }
         }
         int cnt=0;
         for(ll i=0;i<=r-l;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("%d\n",cnt);
         for(ll i=0;i<=r-l;i++)
         {
              if(vec[i].size()==2)
              {
                 printf("%lld %lld %lld\n",i+l,vec[i][0],vec[i][1]);
              }
         }
         return 0;
    }
    
    
    

    我一定可以的!!!

    展开全文
  • ACM程序设计 半素数 题目解释 思路分析 源代码 及扩展
  • 半素数

    千次阅读 2018-04-08 22:18:19
    1187:半素数难度: 秩序白银 时间限制: 1000MS 空间限制: 16MB 提交数: 3 通过数: 1 题目来源: nuistoj题目内容题目描述:An integer greater than one is called primenumber if its only positive ...

    1187:半素数

    难度: 秩序白银    时间限制: 1000MS   空间限制: 16MB   提交数: 3   通过数: 1 题目来源: nuistoj

    题目内容

    题目描述:

    An integer greater than one is called primenumber if its only positive factors are one and itself. For instance,2,11,67,89 are prime numbers but 8,20,27 are not.

    An integer greater than one is called semi-primenumer if it can be decompounded to 2 prime numbers. For example, 6 is asemi-prime number but 12 is not.

    Your task is just to determinate whether a given numberis a semi-prime number.

    输入描述:

    There are several test cases in the input. Each casecontains a single integer N(2<=N<=1000000).

    输出描述:

    One line with a single integer for each case. If thenumber is a semi-prime number, then output "Yes", otherwise"No".

    样例输入:

    3

    4

    6

    12

    样例输出:

    No

    Yes

    Yes

    No


    #include<iostream>
    #include<cmath>
    using namespace std;
    int panduan(int n) {
    	int i;
    	for(i=2; i<=sqrt(n); i++)
    		if(n%i==0)break;
    	if(i>sqrt(n)) return 1;
    	else return 0;
    }
    
    int main() {
    	int n,i,j;
        int t;
    	while(cin>>n) {
               t=0;
    		for(i=2; i<n; i++) {
                	if(n%i==0&&panduan(i)&&panduan(n/i)){
                		t=1;break;
    				}
    		}
    
    		if(t==1)cout<<"Yes"<<endl;
    		else cout<<"No"<<endl;
    	}
    
    	return 0;
    }

    编译中出现的问题:1.对于flag t,没有及时更新它的值,导致下一组数据判断不正确;   2.如果判断两个因数是否为素数,程序提交会超时,所以使用n/i代替另一个因数

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

    千次阅读 2014-02-17 00:37:51
    //质数是大家熟知的概念,我们定义一个半质数的概念:如果一个数恰好是两个质数的乘积(可以相同), //则称它为半质数。前几个半质数是 4, 6, 9, 10, 14, 15, 21, 22, 25, 26。我们的问题是,输入两个正整数x, ...
  • Fermat试验发生器 该存储库包含用于测试用于分解半素数的费马算法、用于相同目的的试除法和半素数生成器的程序。 由 Ludwig Sidenmark 和 Erik V. Kjellberg 制作。
  • jzxx.2120 半质数

    2019-09-17 21:55:32
    质数又称素数,指在大于1的自然数中,只能被1和本身整除的数,也可定义为只有1和本身两个因数的数。而半质数的定义是这样的:若对于一个正整数N,恰好能够分解成两个质数的乘积,它就被称为半质数。比如,4=2*2,15=3...
  • H-半素数是指能写成两个H素数的乘积的H数(这两个数可以相同也可以不同)。输入一个H数h(h <=1000001),输出1~h之间有多少个H-半素数。 分析: 1、筛选法求H素数。 2、再枚举求H-半素数。 #pragma comment(l....
  • 2·14 情人&元宵节专题:半质数的个数 发布公司:有 效 期:赛 区: CSDN  2014-02-14至2014-03-16北京 难 度 等 级:答 题 时 长:编程语言要求: 120分钟C C++ Java C#  题目详情 ...
  • 该函数计算半质数的两个质因数。 如果两个数彼此接近,则使用费马定理。 该函数在密码学中很有用,尤其是 RSA。
  • vector存一下2到他平方根的素数,然后在int main里面写两个循环求出所有的半素数,存起来。然后输入一个数判断在不在半素数表里就行。 我当时做的时候。想的是,写一个判断素数的函数。里面输入一个先判断是不是素数...
  • UVA-11105 H-半素数

    2019-12-26 21:24:22
    =106+1),输出h及以下有多少个H-半素数。 H-半素数的定义:能写成两个H素数的乘积的H数。 H素数的定义:本身不是1,且不能写成两个不是1的数的乘积的H数。 H数的定义:可以表示为4n+1的数,n为任意整数。 一看到...
  • 题目:质数是大家熟知的概念,我们定义一个半质数的概念:如果一个数恰好是两个质数的乘积(可以相同),则称它为半质数。前几个半质数是 4, 6, 9, 10, 14, 15, 21, 22, 25, 26。我们的问题是,输入两个正整数x ...
  • 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 == ...
  • zoj_2723 Semi-Prime 半素数

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

    2016-12-10 15:15:32
    如果一个数能分解为两个素数的乘积,且大于 1,那么,这个数就是半素数。例如,6=2×3,2 和3 都是素数,那么,6 就是半素数。12 就不是半素数。你的任务就是判断一个给定的数字是否是一个半素数。 2
  • 给出一个数N,你的任务是计算1~N中H半素数的个数。   H半 素 数是一个H数,它是两个H素数的乘积。两个H素数可以相等或不同。在上面的例子中,所有五个数字都是H半素数。  125 = 5×5×5不是 H半素数 ,因为...
  • set,分别用来存储素数和半素数。为什么素数的存储不用set呢?因为我们的终极目标不是判断素数,而是半素数。采用vector存储素数有利于线性查找,在for循环中,可直接根据下标遍历素数表。而采用set存储半素...
  • 数学中,两个素数的乘积所得的自然数我们称之为半素数。 现在我们给定一个数N,我们想要得到小于或等于N的半素数的数目。 代码 #include &lt;bits/stdc++.h&gt; using namespace std; vector&lt;int&...
  • 来源:牛客网 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 最近张老师对半素数感兴趣。半素数(semi-prime)是...比如4和10是半素数,因为4=2×...
  • 然后不考虑“H数 ”之外的数,用这里面的数进行素数筛选 将H-素数都筛出来 在最后的时候两重循环枚举素数将他们的乘积标注出来最后 剩下的H数就都会是H-合数了 完整代码 #include #include #include ...
  • 题目大意是让找出100 0000以内的半素数,所谓半素数就是两个素数的积(或者说一个素数的平方); 思路如下: 1.因为数太大,如果一个一个判断很可能会超时,所以要建立半素数表利用检索找到素数; 2.100 0000以内的...
  • Python 如何求素数质数 文章目录Python 如何求素数质数素数质数(重点)方法一:枚举方法二:厄拉多塞筛法【埃氏筛】方法三:线性筛相关博客 素数质数(重点) 先明白什么是素数 质数,英文名:Prime number,...
  •  这道题的基本题意为输入一个数,判断这个数是否为半素数(可以分解成两个素数相乘的数称为半素数)。  基本思路为先判断可以被这个数整除的数是否为素数,然后再判断商是否为素数,如果都为素数,则这个数为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,529
精华内容 4,611
关键字:

半素数