Benchmark for C, Java and Python with prime factorization

After practicing Python, I created a program that calculates prime factorization with simple logic. By the way, I created it in C language and Java and tried to compete for processing speed, so I will upload it.

From the result, the program will be long.

#C language
$ ./a.exe 123456789
123456789 = 3 * 3 * 3607 * 3803
The time required is 2.884932 seconds.

# Java
>java -jar Factorization.jar 123456789
123456789 = 3803 * 3607 * 3 * 3
The journey time is 1245 ms.

# Python3
>python factorization.py 123456789
123456789 = 3 * 3 * 3607 * 3803
The time required is 60.498295 seconds

Java is the top. The reason why Python is slow is that the program I made that has rarely used Python is garbage ^^;

However, I wonder if Java is faster than C. I was wondering, so I decided to change the environment. I used Cygwin as the execution environment for C, but for the sake of fairness !? I'll try running everything on Linux. I used EC2 from AWS. I tried using t2.xlarge a little richly for the purpose of benchmarking with Amazon Linux2 image. (It costs money, so delete it as soon as it's done ;;)

The result is as follows.

[ec2-user ~]$ #C language
[ec2-user ~]$ ./a.out 123456789
123456789 = 3 * 3 * 3607 * 3803
The time required is 2.730501 seconds.
[ec2-user ~]$ #Java
[ec2-user ~]$ java -jar Factorization.jar 123456789
123456789 = 3803 * 3607 * 3 * 3
The journey takes 828 milliseconds.
[ec2-user ~]$ #Python
[ec2-user ~]$ python3 factorization.py 123456789
123456789 = 3 * 3 * 3607 * 3803
The time required is 33.936324 seconds

After all Java is the top. Python is probably the fastest compared to Windows. Personally, I thought that C language was the fastest, so it's a little surprising result, but I think Java's ArrayQueue class is better than creating a queue by yourself. .. ..

The source used is listed below.

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

typedef unsigned long ulong_t;

//Queue to collect prime factors
typedef struct _que {
    ulong_t prime;
    struct _que*  next;
} que_t;

que_t* factrization(ulong_t);
long getusec();

void main(int argc, char** argv){
    ulong_t num;
    char* e;
    num = strtoul(argv[1], &e, 10);

    long before = getusec();
    //Perform prime factorization
    que_t* q = factrization(num);
    long after = getusec();

    //View results
    printf("%d = %d", num, q->prime);
    while(q->next != NULL){
        q = q->next;
        printf(" * %d", q->prime);
    }

    //Display elapsed time
    long spend = (after - before);
    long sec = spend / 1000000;
    long usec = spend % 1000000;
    printf("\n Time required%d.%It's d seconds.\n", sec, usec);
}

//Decompose the passed natural number n into the product of a prime number and a natural number
que_t*  factrization(ulong_t n){
    //Matrix for calculating prime numbers
    // (Since 0 is filled when the memory is allocated, the element containing 0 is a prime number candidate.)
    ulong_t*  p = calloc((n+1), sizeof(ulong_t));

    //Determining prime numbers for the first time from 2
    for(int a = 2; a < (n/2); a++){
        //Skip numbers that have already been confirmed as non-prime numbers
        if(p[a] != 0){
            continue;
        }
        //Remove multiples of prime numbers from candidates
        int b = 2;
        int m = a * b;
        while(m < n){
            p[m] = -1;  //Non-zero ⇒ not a prime number
            b++;
            m = a * b;
        }
        //When n is a multiple(When it is a non-prime number)
        if(n == m){
            // n = a * b(a is a prime number)
//            printf("%d = %d * %d\n", n, a, b);
            //Recursively repeat for b
            que_t* f = factrization(b);
            //Put a in the queue
            que_t* qa = malloc(sizeof(que_t));
            qa->prime = a;
            //Add a to the beginning of the queue
            qa->next = f;
            //Returns the queue
            return qa;
        }
    }
    //If you say to the end, n is a prime number
    //Generate and return a queue
    que_t* qp = malloc(sizeof(que_t));
    qp->prime = n;
    qp->next = NULL;
    free(p);
    return qp;
}

//Current time(Get microseconds)
long getusec(){
    struct timeval _time;
    gettimeofday(&_time, NULL);
    long sec = _time.tv_sec;
    sec *= 1000000;
    long usec = _time.tv_usec;
    return sec + usec;
}
package example;

import java.util.ArrayDeque;
import java.util.Calendar;
import java.util.Iterator;
import java.util.Queue;
import java.util.Scanner;

/**
 *Challenge prime factorization
 */
public class Factrization {

	public static void main(String[] args) {
		int num;
        num = Integer.parseInt(args[0]);

		//Queue to register the decomposed prime factors
		Queue<Integer> queue = new ArrayDeque<>();

		Calendar before = Calendar.getInstance();
		//Perform prime factorization
		queue = fact(num, queue);
		Calendar after = Calendar.getInstance();

		//View results
		Iterator<Integer> i = queue.iterator();
		System.out.printf("%d = %d", num, i.next());
		while (i.hasNext()) {
			System.out.printf(" * %d", i.next());
		}
		System.out.println();
		System.out.printf("The time required is%d milliseconds.\n",
                (after.getTimeInMillis() - before.getTimeInMillis()));
	}

	/**
	 *Decompose the passed natural number into the product of a prime number and a natural number
	 */
	static Queue<Integer> fact(int n, Queue<Integer> q) {
		//Define an array that is a candidate for a prime number.
		//In Java, it is padded with 0s at the time of generation, so elements containing 0s are candidates for prime numbers.
		int[] p = new int[n + 1];
		for (int a = 2; a < (n / 2); a++) {
			//Skip if confirmed as non-prime
			if (p[a] != 0) {
				continue;
			}
			int b = 2;
			int m = a * b;

			while (m < n) {
				p[m] = -1;		//Non-zero ⇒ non-prime element
				b++;
				m = a * b;
			}
			if (n == m) {
//				System.out.printf("%d = %d * %d\n", n, a, b);
				Queue<Integer> f = fact(b, q);
				f.add(a);
				return f;
			}
		}
		q.add(n);
		return q;
	}
}
import sys
import time

#Prime factorization
def factrization(n):
    #Define an integer up to a given number
    p = list(range(n+1))
    #Starting from 2, remove multiples
    #OK if you do up to half of the maximum value
    for a in range(2,int(n/2)):
        #If it is decided that a is not a prime number, go to the next
        if p[a] == 0 :
            continue
        #Number to multiply by prime number
        b = 2
        m = a * b
        #Multiple of a(That is, a number that is not a prime number)To 0
        while m < n:
            p[m] = 0
            b += 1
            m = a * b
        #If n is a multiple of a
        if m == n:
            # n=a*b confirmed
            # print('%d = %d * %d' % (n, a, b))
            #Further factorize b
            fact = factrization(b)
            #Since the confirmed a is a prime number, it is output.
            return [a] + fact
    #If n does not become 0, n is a prime number
    return [n]

#Pass a natural number as a command line argument
num = eval(sys.argv[1])
before = time.time()
#Perform prime factorization
f = factrization(num)
after = time.time()
#Display the execution result
print('%d = %d' % (num, f[0]), end='')
for p in f[1:]:
    print(' * %d' % p, end='')

print('\n Time required%f seconds' % (after - before))

Recommended Posts

Benchmark for C, Java and Python with prime factorization
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
RaspberryPi L Chika with Python and C #
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
MessagePack-Try to link Java and Python with RPC
Causal reasoning and causal search with Python (for beginners)
Wrap C with Cython for use from Python
Wrap C ++ with Cython for use from Python
Investigate Java and python data exchange with Apache Arrow
Programming with your smartphone anywhere! (Recommended for C / Python)
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
Programming with Python and Tkinter
Python and hardware-Using RS232C with Python-
ABC163 C problem with python3
Python, Java, C ++ speed comparison
Determine prime numbers with python
I compared Java and Python!
Fibonacci and prime implementations (python)
python with pyenv and venv
ABC188 C problem with python3
Prime factorization with O (n ^ (1/4))
ABC187 C problem with python
Works with Python and R
Solving with Ruby and Python AtCoder ARC 059 C Least Squares
Mandelbrot Benchmark (C, PHP, HHVM, Ruby, Python, PyPy, and Kinx)
Installation procedure for Python and Ansible with a specific version
Analyze stocks with python and look for favorable trading phases
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
Library for specifying a name server and dig with python
This and that for using Step Functions with CDK + Python
Have Google Text-to-Speech create audio data (narration) for video material (with C # and Python samples)
Communicate with FX-5204PS with Python and PyUSB
Shining life with Python and OpenCV
Solve ABC163 A ~ C with Python
Difference between java and python (memo)
Robot running with Arduino and python
Call C from Python with DragonFFI
Install Python 2.7.9 and Python 3.4.x with pip.
Java and Python basic grammar comparison
Create Awaitable with Python / C API
Neural network with OpenCV 3 and Python 3
Scraping with Node, Ruby and Python
Scraping with Python, Selenium and Chromedriver
Create a striped illusion with gamma correction for Python3 and openCV3
Scraping with Python and Beautiful Soup
Getting Started with Python for PHPer-Classes
Python cheat sheet (for C ++ experienced)
JSON encoding and decoding with python
Hadoop introduction and MapReduce with Python
[GUI with Python] PyQt5-Drag and drop-
Solve ABC168 A ~ C with Python
Reading and writing NetCDF with Python
Tips for calling Python from C
I played with PyQt5 and Python3
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum