Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdlib.h>
- #include <stdio.h>
- #include <math.h>
- int is_prime(int n) {
- if(n <= 1) {
- return -1;
- }
- int i;
- for(i = 2; i <= sqrt(n); i++) {
- if(n % i == 0) {
- return 0;
- }
- }
- return 1;
- }
- float euler_f(int n) {
- int last_prime = 0, i = 2;
- float e = n;
- while(n != 1) {
- if(n % i == 0 && is_prime(i)) {
- if(last_prime != i) {
- e = e * (1.0 - 1.0 / i);
- last_prime = i;
- }
- n = n / i;
- } else {
- i += 1;
- }
- }
- return e;
- }
- int main(int argn, char ** argv) {
- int number = atoi(argv[1]);
- int bound = atoi(argv[2]);
- int i;
- printf("Numbers that match: ");
- for(i = 1; i < bound; i ++) {
- if(euler_f(i) == number) {
- printf("%d, ", i);
- }
- }
- printf("\n");
- return 0;
- }
- // The Euler function φ: N → N is a mapping associating to each positive integer n the number φ(n), which is the number of integers that are relatively prime to n.
- // For example φ(6) = 2 because only 1 and 5 are relatively prime to 6.
- // The formula for finding such a number is the following:
- // given n, φ(n) = n * (1 - 1 / P1) * ... * (1 - 1 / Pi), P1 to Pi being the set of prim factors of n
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement