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