距离的总和
题目描述:
定义两个大于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;}
#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; }
#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; }
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()
#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;
}
//system("pause"); return 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;}
/* 思路 先将数据升序排序 然后计算每个数据到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; }
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; }
//判断出规律,每个数据段的素数计算了多少次 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); } };
#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;}
}