ProjEuler/203.cpp at master · vam54ee/ProjEuler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<vector>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

vector<long long> generateSieve(long long size)
{
  vector<long long> primes = vector<long long>(size+1, 0);
  vector<long long> finalPrimes;
  primes[2] = 1;
  primes[3] = 1;
  primes[5] = 1;
  primes[7] = 1;
  for(long long i = 8; i < size; i++)
  {
    if(i%2 == 1)
      primes[i] = 1;
    else
      primes[i] = 0;
  }

  for(long long i = 3; i < size/2; i+=2)
  {
    for(long long j= 3; i*j < size; j+=2)
    {
      primes[i*j] = 0;
    }
  }
  cout<<"done"<<endl;
  for (long long i = 0; i < size+1;i++)
  {
    if(primes[i] == 1)
      finalPrimes.push_back(i);
  }
  cout<<"done with final primes with length"<<finalPrimes.size()<<endl;
  return finalPrimes;
}

long long nCr(int n, int r) {
    if(r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}


int main()
{
  vector<long long> finalPrimes = generateSieve(100000000);
  vector<long long> uniqueArr;
  uniqueArr.push_back(1);

  for (long long i = 2; i <= 50; i++) {
    for(long long j = 1; j <= i/2; j++) {
      long long elem = nCr(i,j);
      bool found = false;
      for (size_t i = 0; i < uniqueArr.size(); i++) {
        if(uniqueArr[i] == elem) {
          found = true;
          break;
        }
      }
      if(!found) {
        uniqueArr.push_back(elem);
      }
      // cout<<elem<<endl;
    }
  }

  vector<long long> ans;

  for (long long i = 0; i < uniqueArr.size(); i++) {
    long long isFree = true;
    for(long long j = 0; j < sqrt(uniqueArr[i]); j++) {
      if(uniqueArr[i]%(finalPrimes[j]*finalPrimes[j]) == 0){
        isFree = false;
        break;
      }
    }
    if(isFree) {
      ans.push_back(uniqueArr[i]);
    }
  }
  cout<<ans.size()<<endl;
  long long ansSum = 0;
  for (size_t i = 0; i < ans.size(); i++) {
    cout<<ans[i]<<endl;
    ansSum += ans[i];
  }
  for (size_t i = 0; i < uniqueArr.size(); i++) {
    cout<<uniqueArr[i]<<endl;
  }
  cout<<ansSum<<endl;
  // ans.forEach(function(item){ansSum += parseInt(item);})
  // console.log(ans,ansSum);

  // long long uniq = Object.keys(uniqueArr);
  // long long ans = [];
  // for (long long i = 0; i < uniq.length; i++) {
  //   long long isFree = true;
  //   for(long long j = 0; j < Math.sqrt(uniq[i]); j++) {
  //     if(uniq[i]%(finalPrimes[j]*finalPrimes[j]) == 0){
  //       isFree = false;
  //       break;
  //     }
  //   }
  //   if(isFree) {
  //     ans.push(uniq[i]);
  //   }
  // }
  // long long ansSum = 0;
  // ans.forEach(function(item){ansSum += parseInt(item);})
  // console.log(ans,ansSum);
  // // console.log(uniqueArr, Object.keys(uniqueArr).length);

	return 0;
}