首页 > 试题广场 >

距离的总和

[问答题]

距离的总和


题目描述:

定义两个大于2的偶数之间的距离,为这两个数之间质数的个数。从小到大输入n个大于2的偶数,输出所有数两两之间距离的总和(应该有n*(n-1)/2个距离,输出总和就好)。

输入

第一行是输入偶数的个数,最小为2,最大可能到几万。之后每行为一个偶数,最小是4,最大可能是几百万,不重复的升序排列。

输出

输入数据两两间距离的总和,这应该是一个不小于0的整数。

样例输入

3
4
6
12

样例输出

6

//假设有n个数,每相邻两个数有一个区间,则有n-1个相邻区间。设每个区间的距离(质数个数)为di,i=0,1,n-2.
//在计算所有数据两两之间的距离总和时,会发现第一个距离d0被包含了n-1次(第一个数分别和之后所有n-1个数构成区间);
//第二个距离d1则被包含了2*(n-2)次;
//第三个距离d2被包含了3*(n-3)次;
//...
//第n-1个距离d(n-2)被包含了(n-1)*(n-(n-1))=n-1次
//对这些距离求和,即为总距离之和ans=1*(n-1)*d0+...+i*(n-i)*d(i-1)+...+(n-1)*(n-(n-1))*d(n-2)
#include <stdio.h>
#include <vector>
#include <iostream>
#include <math.h>
using namesapce std;
int getprimenum(int a, int b)
{
    int count=0;
    for(int i=a+1; i<b; i++)
    {
        int j=2;
        for(; j<=sqrt(double(i)); j++)
        {
            if(i%j == 0)
                break;
        }
        if(j>sqrt(double(i)))
            count++;
    }
    return count;
}
int main(int argc, char** argv)
{
    int n;
    cin>>n;
    vector<int> data(n);
    for(int i=0; i<n; i++)
        cin>>data[i];
    //统计每两个相邻偶数区间的质数个数(n个质数,有n-1个区间)
    vector<int> count(n-1);
    for(int i=1; i<n; i++)
        count[i-1] = getprimenum(data[i-1], data[i]);
    //计算所有数据两两之间的距离总和
    int ans=0;
    for(int i=1; i<n; i++)
        ans += i*(n-i)*count[i-1];
    cout<<ans<<endl;
    return 0;
}

编辑于 2017-08-18 11:46:53 回复(3)
#include<iostream> #include<vector> using namespace std; int primeCount(vector<int> vec, int num1, int num2) { int count = 0; for (int i = vec[num1]+1; i < vec[num2]; i++) { int j; bool flag = true; for (j = 2; j <= sqrt(i); j++) { if (i % j == 0) { flag = false; break; } } if (flag) count++; } return count; } int sumOfTwonumber(vector<int> vec, int num1, int num2) { int sum = 0; for (int i = num1; i <=num2; i++) sum += vec[i]; return sum; } int main() { int n; cin >> n; vector<int> vec; vector<int> primeNumber; for (int i = 0; i < n; i++) { int number; cin >> number; vec.push_back(number); } int count = 0; int p1 = 0; int p2 = 1; while (p1 < n&&p2 < n) { count = primeCount(vec, p1, p2); primeNumber.push_back(count); p1++; p2++; } int result=0; for (int i = 0; i < n-1; i++) { for (int j = i ; j < n-1; j++) { int temp = sumOfTwonumber(primeNumber, i, j); result += temp; } } cout << result << endl; return 0; }
编辑于 2017-08-15 12:03:41 回复(0)
#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <climits>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define inf 0x3f3f3f3f
#define ll long long
#define fora(i,a,n) for(int i=a;i<=n;i++)
#define fors(i,n,a) for(int i=n;i>=a;i--)
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
const int maxn = 100024;
const int mod = 1e9 + 7;
const double eps = 1e-8;
using namespace std;
typedef pair<int, int> pr;
int n;
int a[maxn];
int isNP[maxn];
int allP[maxn];
int tot;
void getPrime() {
    for (int i = 2; i <= a[n]; i++) {
        if (!isNP[i]) {
            allP[tot++] = i;
            //printf("i : %d\n", i);
                for (int j = i << 1; j <= a[n]; j += i) {
                    isNP[j] = 1;
                }
        }
    }

}
int  main(){
#ifdef CDZSC_OFFLINE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
#endif


    tot = 0;
    memset(isNP, 0, sizeof(isNP));
    sci(n);
    fora(i, 1, n) {
        sci(a[i]);
    }    
    getPrime();
    int now = 1;
    int sum = 0;

    fora(i, 0, tot - 1) {
        while(a[now]<allP[i] && now <=n){
            now++;
            break;
        }
        sum += (now - 1)*(n - now + 1);
        //printf("%d\n", sum);
    }
    //printf("tot : %d\n", tot);
    printf("%d\n", sum);
    return 0;
}



发表于 2019-03-12 12:38:22 回复(0)
#include<iostream>
using namespace std;
//判断是质数
bool IsZhishu(const int &a)
{
 if(a<2)
  return 0;
 for(int i=2;i<a;i++)
  if(a%i==0)
   return 0;
 return 1;
}
//计算距离
int Distance(const int &a,const int &b)
{
 if((a<=2)||(b<=2))
  {
   cout<<"必须大于2"<<endl;
   return -1;
   }
 int count=0;
 if((a%2!=0)||(b%2!=0))
  {
    return count;   
  }
 for(int i=a+1;i<b;i++)
  if(IsZhishu(i))
   count++;
 return count;
}
//main test
int main()
{
 cout<<"样例输入:"<<endl;
 int num;
 cin>>num;
 int *a=new int[num];
 for(int i=0;i<num;i++)
  cin>>a[i];
 int sum=0;
 for(int i=0;i<num;i++)
  for(int j=i+1;j<num;j++)
   sum+=Distance(a[i],a[j]);
 cout<<"样例输出:"<<endl;
 cout<<sum<<endl;
 delete[] a;
 system("pause");
 return 0;
}

发表于 2018-09-26 12:52:32 回复(0)
def distant(a,b): #求取两数的距离,距离定义为两数之间素数的个数,a和b为偶数且b>a
    if a>b:
        a,b=b,a
    return distantTozero(b)-distantTozero(a)

def distantTozero(x): #求一个自然数到0的距离,距离定义为0到a之间素数的个数
    count=1
    for i in range(2,x):
        for j in range(2,i+1):
            if i%j==0:
                break
            elif j==(i-1):
                count=count+1
                break
    return count

numb=int(input("请输入偶数的个数:\n"))
list_oushu=[]
print("请输入偶数序列:\n")
while True:

    a=0
    a=input()
    if a=="":
        print(a)
        break
    try:
        b=int(a)
        list_oushu.append(b)
    except:
        print("请输入数字!\n")
sum=0
for x in range(len(list_oushu)):
    for y in range(len(list_oushu)):
        a=distant(list_oushu[x],list_oushu[y])
        sum=sum+a
print(sum/2)

input("press any key to exit......")
exit()


发表于 2017-12-06 23:38:16 回复(0)
var arr=[3,6,9,8]; function getlength(arr){ return (arr.length*(arr.length-1))/2; } console.log(getlength(arr)); 以上仅为我的个人思路,是否有错还望懂得的人能够指正
发表于 2017-11-20 01:11:04 回复(0)
#include <iostream>
using namespace std;
//判断是否为质数
bool JudgePrimeNumber(int num)
{
    for (int i = 2; i <= sqrt(num); i++)
        if (num % i == 0)
            return false;
    return true;
}

//计算两个数之间的距离
int DistanseSum(int start, int end)
{
    int count = 0;
    for (int i = start; i <= end; i++)
    {
        if (JudgePrimeNumber(i))
            count++;
    }
    return count;
}

int main()
{
    int N = 0;
    cin >> N;
    int* numbersArray = new int[N];

    //虽然没有在线判定,还是要注意一下输入数据的正确性。
    for (int i = 0; i < N; i++)
    {
        cin >> numbersArray[i];
        if (numbersArray[i] < 2)
            return -1;
        if (i > 0 && numbersArray[i] <= numbersArray[i - 1])
            return -1;
    }

    int sum = 0;
    //遍历任意两点距离
    for (int i = 0; i < N - 1; i++)
        for (int j = i + 1; j < N; j++)
        {
            sum += DistanseSum(numbersArray[i], numbersArray[j]);
        }
    
    delete[] numbersArray;
    //cout << sum << endl; //system("pause");
    return sum;
}

编辑于 2017-09-08 10:49:25 回复(0)
#include<iostream>
#include<vector>
using namespace std;
bool isPrime(int x){
 bool isTrue = true;
 int i = 2;
 while (i <= sqrt(x)){
  if (x%i == 0){
   isTrue = false;
   break;
  }
  i++;
 }
 return isTrue;
}

long long numPrime(int x, int y){
 int i;
 int sum = 0;
 for (i = x; i <= y; i++){
  if (isPrime(i))
   sum++;
 }
 return sum;
}
int main(){
 int n;
 cin >> n;
 vector<int> num(n);
 int i,j;
 for (i = 0; i < n; i++)
  cin >> num[i];
 long long sum = 0;
 for (i = 0; i < (int)num.size() - 1; i++){
  for (j = i + 1; j < (int)num.size(); j++){
   sum += numPrime(num[i], num[j]);
  }
 }
 cout << sum << endl;
 //system("pause");
 return 0;
}

发表于 2017-09-08 10:24:41 回复(0)
/*我这里iostream一直有红色下划线提示,难道是编译环境不认识吗?
大家帮忙看看我的思路对不对。
首先对说有偶数排序,然后依次求每个数和所有 后面数的距离,求和
*/
#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    int n;
    cin >> n;
    int p;
    vector<int> o;
    for(int i = 0; i < n; i++){
        cin >> p;
        o.push_back(p);
    }
    sort(o.begin(),o.end());
    int sum = 0;
    int g = 0;
for (int i = 0; i < o.size()-1; i++){ g = 1; if (g <= o.size() - 1){ for (int j = o[i]; j < o[i + g]; j++){ g++; for (int q = 2; q <= sqrt(j); q++){ if (j % q != 0) sum++; } } } } cout << sum << endl;
return 0;
}

发表于 2017-09-07 11:22:36 回复(0)
/*
思路
先将数据升序排序
然后计算每个数据到0的距离存于数组d中
先计算最小的距离d[0]与其他距离的距离差,再计算次小的距离d[1]与其他距离的距离差...以此类推,最后 总距离需要减去(n-1)*d[0]、(n-2)*d[1]、....、1*d[n-2]  (即(n-1-i)*d[i])
总距离需要加上1*d[1]、2*d[2]、....、(n-1)*d[n-1]  (即i*d[i])
*/


#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
using namespace std;
void Qsort(int a[], int low, int high)//快排
{
	if (low >= high)
		return;
	int first = low;
	int last = high;
	int key = a[first];
	while (first < last)
	{
		while (first < last&&key <= a[last])
			last--;
		a[first] = a[last];
		while (first < last&&key >= a[first])
			first++;
		a[last] = a[first];
	}
	a[first] = key;
	Qsort(a, low, first - 1);
	Qsort(a, first + 1, high);
}
bool func1(int a)//判断素数
{
	if (a == 2 || a == 3)
		return true;
	for (int i = 2; i*i <= a; i++)
		if (a%i == 0)
			return false;
	return true;
}
int func2(int n)//返回小于等于n的素数个数
{
	int count = 0;
	count += 2;
	for (int i = 4; i <= n; i++)
	{
		if (func1(i))
			count++;
	}
	return count;
}
int main(){
	long long n;
	long long res;
	long long i, j,k;
	int x,y,z;
	while (cin >>n)
	{
		res = 0;
		int *a = new int[n];
		int *d = new int[n];
		int *DP1 = new int[n];//前i个a元素中 包含a[i]的连续最长递增子序列
		int *DP2= new int[n];//后N-i个a元素中 包含a[i]的连续最长递增子序列
		for (i = 0; i < n; i++)
			cin >> a[i];
		Qsort(a, 0, n - 1);
		for (i = 0; i < n; i++)
			d[i] = func2(a[i]);
		for (i = 1; i < n; i++)
		{
			res += i*d[i];
		}
		for (i = 0; i < n-1; i++)
		{
			res -= (n-1-i)*d[i];
		}
		cout <<res<< endl;
	}
	return 0;
}

发表于 2017-09-04 16:08:15 回复(0)
int primOfCount(int num1,int num2)
{
	int count = 0;
	for (num1 = num1+1;num1 < num2;num1+=2)
	{
		bool flag = true;  
		for(int i = 2;i <= sqrt(num1);i++)//
		{
			if (num1%i == 0)
			{
				flag = false;
				break;
			}
		}
		if (flag)
		{
			//cout<<"num1 "<<num1<<endl;
			count++;
		}

	}
	return count;
}

int main()
{
	int n,a;
	int cnt = 0;
	cin>>n;
	vector<int>vec;
	for (int i = 0; i < n; i++)
	{
		cin>>a;
		vec.push_back(a);
	}
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i+1; j < n ; j++)
		{
	       cnt += primOfCount(vec[i],vec[j]);
		}
	}
	cout<<cnt<<endl;
	return 0;
}

发表于 2017-08-27 17:39:18 回复(0)
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool checkPrime(vector<int> &formerPrimes, int k) {
    for (auto prime : formerPrimes) {
        if (k%prime == 0) return false;
    }
    return true;
}

int main(int argc, char *argv[])
{
    int n = 0;
    cin >> n;
    vector<int> nums(n), primes;
    for (int i = 0; i < n; ++i)
        cin >> nums[i];

    primes.push_back(2);
    int res = 0, start = 3;
    int cnt = 1, former = 0;

    while (start <= nums.front()) {
        if (checkPrime(primes, start))
            primes.push_back(start);
        ++start;
    }
    for (int i = 1; i < n; ++i) {
        int nowcnt = 0;
        while (start <= nums[i]) {
            if (checkPrime(primes, start)) {
                primes.push_back(start);
                ++nowcnt;
            }
            ++start;
        }
        res += nowcnt*cnt + former;
        former = nowcnt;
        ++cnt;
    }
    cout << res << endl;
    return 0;
}
发表于 2017-08-17 17:58:13 回复(0)
/*
 * 现在有两个点A、B(A<B),则AB之间所有线段的和即AB
 * 如果现在在B的右边加一个点C,则AC之间相对AB来说,线段多了AC和BC,
 * AC之间所有线段的和即AB+AC+BC,将AC分解为AB+BC,则AB+AC+BC=AB*2+BC*2
 * 现在推广到4个点A、B、C、D时,所有线段的和为
 * AB*1*(4-1)+BC*2*(4-2)+CD*3*(4-3)
 * 推广到n个点的时候,(L(n)表示最后一段线段的长度)
 * AB*1*(n-1)+BC*2*(n-2)+CD*3*(n-3)+...+L(n)*n*1
 *
 * 现在回头看本题,可以将两个相邻正偶数之间的距离(即质数的个数)看做线段的长度
 * 然后套用上面的公式来求距离之和
 *
 * 求两个正偶数之间质数的个数,可以直接统计质数的个数,也可以用筛选法来求
 * 求4-66666666之间质数的个数,直接统计用时1200s,用筛选法来求用时950s
 * 题目要求最大的数是万这个级别,所以建议使用筛选法,速度相对会快很多
 */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Timers;


namespace TestForCSharp
{
    class Program
    {
        /// <summary>
        /// 判断n是否为质数
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        static bool IsPrime(int n)
        {
            for (int i = 2; i <= Math.Sqrt(n); i++)
            {
                if (n % i == 0)
                    return false;
            }
            return true;
        }

        /// <summary>
        /// 计算m和n之间质数的个数
        /// </summary>
        /// <param name="m">区间的左端点</param>
        /// <param name="n">区间的右端点</param>
        /// <returns></returns>
        static int CountPrime(int m, int n)
        {
            int count = 0;
            for (int i = m + 1; i < n; i++)
            {
                if (IsPrime(i))
                    count++;
            }
            return count;
        }

        /// <summary>
        /// 计算m和n之间质数的个数
        /// </summary>
        /// <param name="prime"></param>
        /// <param name="m"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        static int CountPrime(bool[] prime, int m, int n)
        {
            int count = 0;
            for (int i = m ; i <= n; i++)
            {
                if (prime[i]==true)
                    count++;
            }
            return count;
        }

        static void Main(string[] args)
        {
            string line;
            while (!string.IsNullOrEmpty(line = Console.ReadLine()))
            {
                int n = Convert.ToInt32(line);
                int[] numbers = new int[n];
                string[] s = Console.ReadLine().Split(' ');
                for (int i = 0; i < n; i++)
                {
                    numbers[i] = Convert.ToInt32(s[i]);
                }

                int sum = 0;

                //方法一:用判断每个数是否为质数的方法,求出每个区间中质数的个数
                //int[] distances = new int[n - 1];
                //DateTime startTime = DateTime.Now;

                //for (int i = 0; i < n-1; i++)
                //{
                //    int distances = CountPrime(numbers[i], numbers[i + 1]);
                //    sum += distances * (i + 1) * (n - i-1);
                //}

                //方法二:用筛选法求出每个区间中质数的个数
                //需要维护一个从0到最大数的bool数组,prime[i]==true表示i为质数
                bool[] prime = new bool[numbers[n-1]+1];

                //将所有奇数置为true(偶数默认赋值为false,因为偶数不可能是质数)
                for (int i = 2; i < numbers[n - 1]; i += 2)
                {
                    //prime[i - 1] = false;
                    prime[i + 1] = true;
                }

                //将prime[2]置为true,因为2是质数
                prime[2] = true;

                //所有质数的倍数都不是质数
                for (int i = 3; i <= numbers[n - 1]; i++)
                {
                    if (prime[i] == true)
                    {
                        if (IsPrime(i))
                        {
                            //将i的倍数置为false
                            for (int j = i * 2; j < numbers[n-1]; j += i)
                                prime[j] = false;
                        }
                        else
                            prime[i] = false;
                    }
                }

                for (int i = 0; i < n - 1; i++)
                {
                    int distance = CountPrime(prime, numbers[i], numbers[i + 1]);
                    sum += distance * (i + 1) * (n - i -1);
                }




                //DateTime endTime = DateTime.Now;
                Console.WriteLine(sum);
                //Console.WriteLine((endTime - startTime).TotalSeconds);
            }
        }

    }
}
发表于 2017-08-15 19:25:05 回复(0)
//判断出规律,每个数据段的素数计算了多少次
class Solution {
public:
	int distance(int len,int arr[])
	{
		int result = 0;
		if (len < 2)
			return 0;
		for (int i = 0; i < len-1; i++)
		{
			result += (i+1)*(len - i - 1)*primenum(arr[i], arr[i + 1]);
		}
		return result;
	}

	//给出这个数据段的素数个数
	int primenum(int left, int right)
	{
		int cnt = 0;
		for (int i = left + 1; i <= right; i += 2)
		{
			if (isprime(i))
				cnt++;
		}
		return cnt;
	}

	//判断数字是否为素数
	bool isprime(int num)
	{
		bool result = true;
		for (int i = 2; i < num / 2+1;i++)
		if (num%i == 0)
		{
			result = false;
			break;
		}
		return result;
	}

	void test()
	{
		int n;
		cin >> n;
		int *arr = new int[n];
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		cout << distance(n, arr);
	}
};

发表于 2017-08-15 16:49:17 回复(0)
#include<iostream>
#include<cstring>
usingnamespacestd;
 
intfun(intm, intn)//两个数之间的质数个数
{
    intnum = 0;
     
    for(inti = m; i <= n; i++)
    {
        inttemp = 0;
        for(intj = 2; j <= sqrt(i); j++)
        {
            if(i%j == 0) temp++;
        }
 
        if(temp == 0) num++;
    }
    returnnum;
}
 
intmain()
{
    intfun(intm, intn);
    intgeshu;
    cin >> geshu;
    intt = 0;
    intnumber;
    intshuzu[100];
    for(intt = 0; t < geshu; t++)
    {
        cin >> number;
        shuzu[t] = number;
         
    }
 
    //计算两两数之间的质数,并求和。
    ints=0;
    intsum = 0;
    for(inti = 0; i < geshu; i++)
    {
        for(intj = i + 1; j < geshu; j++)
        {
             
                s = fun(shuzu[i], shuzu[j]);
                sum = sum + s;
             
        }
    }
     
     
    cout << sum << endl;
}

发表于 2017-08-15 11:45:12 回复(0)
#include<iostream> #include<vector> #include<cmath> using namespace std; int main(){ int n; freopen("in.txt","r",stdin); cin >> n; vector<int> A(n); for(int i = 0;i < n;i++) cin >> A[i]; vector<int> count(n-1); int sum = 0; for(int i = 0;i < n-1;i++){ int start = A[i] + 1; int end = A[i+1]; for(int j = start;j < end;j+=2){ int k; for(k = 2;k <= sqrt(j);k++) if(j% k == 0) break; if(k > sqrt(j)) count[i]++; } sum += (i+1)*(n - 1 - i)*count[i]; } cout << sum << "\n"; return 0; }</int></int></cmath></vector></iostream>
发表于 2017-08-14 20:53:40 回复(0)
int main()
{
int n,a;
vector<int> Vec;
vector<vector<int>> Disk;
int alldisk = 0;

cin >> n;
for(int i = 0; i < n;i ++){
cin >> a;
Vec.push_back(a);
vector<int> A;
Disk.push_back(A);
for(int j =0;j < n; j++){
Disk[i].push_back(0);
}
}
//给出第一个到其他的值
for(int i =1;i < n;i++){
Disk[0][i] = Disk[0][i-1] + Get_num(Vec[i-1],Vec[i]);
Disk[i][0] = Disk[0][i];
}

for(int i = 1; i < n; i++){
for(int j = j; j < n; j++){
Disk[i][j] = Disk[0][j] - Disk[0][i];
Disk[j][i] = Disk[i][j];
}
}

for(int i = 0;i < n; i++){
for(int j = 0; j < i;j++)
alldisk += Disk[i][j];
}

cout << alldisk << endl;
        return 0;
}
发表于 2017-08-14 17:38:31 回复(0)
#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int Fun(int a,int b)
{
int k=0;
for(int i=a;i<=b;i++)
{
for(int j=2;j<=sqrt(i);j++)
{
if(i%j == 0)
{
k++;
break;
}
}
}
return b-a+1-k;
}

int main()
{
int m;
cin>>m;
int n;
int i=0;
int sum=0;
vector<int> arr;
while(i<m)
{
cin>>n;
arr.push_back(n);
i++;
}
for(i=0;i<m-1;i++)
{
for(int j=1;j<m;j++)
{
sum+=Fun(arr[i],arr[j]);
}
}
cout<<sum;
    return 0;
}
发表于 2017-08-13 22:41:00 回复(0)
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>     
#include <math.h>
#include <vector>
#include <sstream>    
#include <queue>
#include <stack>
#include<iomanip>
#include<map>
using namespace std;

bool is_zhishu(int x){
int xt=x;
for (int i=2;i<=sqrt(xt*1.0);i++){
if (xt%i==0)
return false;
}
return true;
}
int calT(int x,int y){
if (x>y){
int temp=x;
x=y;
y=temp;
}
int times=0;
for (int i=x;i<=y;i++){
if (is_zhishu(i))
times++;
}
return times;
}
int main()
{
int n;
while (cin>>n)
{
vector<int> an(n,0);
for (int i=0;i<n;i++)
cin>>an[i];
int num=0;
for (int i=0;i<n;i++)
{
for (int j=i+1;j<n;j++){
num+=calT(an[i],an[j]);
}
}
cout<<num<<endl;
}
return 0;
}

发表于 2017-08-13 11:06:08 回复(0)
求第一个数和最后一个数之间的质数个数,然后乘以数目-1应该就是答案了,不过要注意的是数据类型要用long long ,然后用筛选法求质数数目,不知道有没有大牛来给个答案。

#include<iostream>

using namespace std;

int main()
{
    long int number;
    long long min_nuber,max_number;
    cin>>number;
    cin>>min_nuber;
    while(cin>>max_number);
   
    // 筛选法求质数,为0代表是质数
    bool Zhishu[max_number+1]={0};
   
    Zhishu[0] = 1;
    Zhishu[1] = 1;
    long long number_of_zhishu = 0;
   
    for(long long i=2;i<=max_number;++i)
    {
        if(Zhishu[i]==0)
        {
            number_of_zhishu++;
            for(long long j=2*i;j<=max_number;j+=i)
            {
                Zhishu[j] = 1;
            }
        }
    }
   
    // 实际上每个被计算了 n-1 次
    cout<<number_of_zhishu*(number-1);
   
    return 0;
}
编辑于 2017-08-11 16:45:44 回复(0)