UVa 884 – Factorial Factors

UVa 884 – Factorial Factors

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

UVa 884 - Factorial Factors此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

题目:输出n!中素数因数的个数。

分析:数论。这里使用欧拉筛法计算素数,在计算过程中求解就可以。

            传统筛法是利用每一个素数,筛掉自己的整数倍;

            欧拉筛法是利用当前计算出的全部素数,乘以当前数字筛数;

            所以每一个前驱的素椅子个数一定比当前数的素因子个数少一个。

说明:重新用了“线性筛法”。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

int prime[1000001];
int visit[1000001];
int numbe[1000001];
int sums[1000001];

int main()
{
	//筛法计算素数 
	memset(visit, 0, sizeof(visit));
	memset(numbe, 0, sizeof(numbe));
	int count = 0;
	for (int i = 2 ; i < 1000001 ; ++ i) {
		if (!visit[i]) {
			prime[count ++] = i;
			numbe[i] = 1;
		}
		for (int j = 0 ; j < count && i*prime[j] < 1000001 ; ++ j) {
			visit[i*prime[j]] = 1;
			numbe[i*prime[j]] = numbe[i]+1;
		}
		sums[i] = sums[i-1] + numbe[i];
	}
	
	int n;
	while (~scanf("%d",&n))
		printf("%d\n",sums[n]);
		
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117925.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 常见几种java排序算法

    常见几种java排序算法1.插入排序publicclassInsertSort{publicstaticvoidsort(int[]arr){if(arr.length&amp;amp;amp;gt;=2){for(inti=1;i&amp;amp;amp;lt;arr.length;i++){//挖出一个要用来插入的值,同时位置上留下…

  • Java 流程控制

    Java 流程控制

  • Map – LinkedHashSet & LinkedHashMap 源码解析「建议收藏」

    Map – LinkedHashSet & LinkedHashMap 源码解析「建议收藏」总体介绍如果你已看过前面关于HashSet和HashMap,以及TreeSet和TreeMap的讲解,一定能够想到本文将要讲解的LinkedHashSet和LinkedHashMap其实也是一回事。LinkedHashSet和LinkedHashMap在Java里也有着相同的实现,前者仅仅是对后者做了一层包装,也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。因此本文将重点分析LinkedHashMap。LinkedHashMap实现了Map接口,即允许放入key

    2022年10月12日
  • kafka是什么?主要用在什么场景

    kafka是什么?主要用在什么场景1、kafka是什么?Kafka是由LinkedIn开发的一个分布式基于发布/订阅的消息系统,使用Scala编写,它以可水平扩展和高吞吐率而被广泛使用。2、产生背景Kafka是一个消息系统,用作LinkedIn的活动流(ActivityStream)和运营数据处理管道(Pipeline)的基础。活动流数据是几乎所有站点在对其网站使用情况做报表时都要用到的数据中最常规的部分。活动数据包括页…

    2022年10月13日
  • 根据两点经纬度计算距离

    根据两点经纬度计算距离在实际应用当中,一般是通过一个个体的编码来查找该编码对应的地区中心的经纬度,然后再根据这些经纬度来计算彼此的距离,从而估算出某些群体之间的大致距离范围(比如酒店旅客的分布范围-各个旅客的邮政编码对应的经纬度和酒店的经纬度所计算的距离范围-等等)。用GPS测出两个点的经纬度后,如何计算这两个点之间的距离呢?设两点A、B的经、纬度分别为(jA,wA)(jB,wB),则半径为

  • 渗透测试神器Nessus使用教程「建议收藏」

    渗透测试神器Nessus使用教程「建议收藏」简介:

    2022年10月19日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号